Polynomial and Extensible Solutions in Lock-Chart Solving

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F16%3A00311856" target="_blank" >RIV/68407700:21230/16:00311856 - isvavai.cz</a>

Výsledek na webu

<a href="http://dx.doi.org/10.1080/08839514.2017.1279110" target="_blank" >http://dx.doi.org/10.1080/08839514.2017.1279110</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1080/08839514.2017.1279110" target="_blank" >10.1080/08839514.2017.1279110</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Polynomial and Extensible Solutions in Lock-Chart Solving

Popis výsledku v původním jazyce

Lock-chart (also known as master-key system) solving is a process for designing mechanical keys and locks so that every key can open and be blocked in a user-defined set of locks. We present several algorithms as a result of our 3 years industrial collaboration project, chosen by their asymptotic time complexity and extensibility, which is the ability to add new keys and locks and satisfy the previously unforeseen blocking requirements. Our strongest result is a linear-time algorithm to find the largest diagonal lock-chart with a condition on mechanical properties of keys. Without these restrictions, but given a solution for master keys, the problem is translated into a maximum independent set problem and a greedy approximation is proposed. We evaluate the algorithms on a generated dataset using a non-backtracking procedure to simulate minimal extensions. Both approaches are suggested as heuristics or subroutines for a backtracking constraint satisfaction problem-based (CSP) solver.

Název v anglickém jazyce

Polynomial and Extensible Solutions in Lock-Chart Solving

Popis výsledku anglicky

Lock-chart (also known as master-key system) solving is a process for designing mechanical keys and locks so that every key can open and be blocked in a user-defined set of locks. We present several algorithms as a result of our 3 years industrial collaboration project, chosen by their asymptotic time complexity and extensibility, which is the ability to add new keys and locks and satisfy the previously unforeseen blocking requirements. Our strongest result is a linear-time algorithm to find the largest diagonal lock-chart with a condition on mechanical properties of keys. Without these restrictions, but given a solution for master keys, the problem is translated into a maximum independent set problem and a greedy approximation is proposed. We evaluate the algorithms on a generated dataset using a non-backtracking procedure to simulate minimal extensions. Both approaches are suggested as heuristics or subroutines for a backtracking constraint satisfaction problem-based (CSP) solver.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

20201 - Electrical and electronic engineering

Projekt

—

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2016

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

Applied Artificial Intelligence

ISSN

0883-9514

e-ISSN

1087-6545

Svazek periodika

30

Číslo periodika v rámci svazku

10

Stát vydavatele periodika

GB - Spojené království Velké Británie a Severního Irska

Počet stran výsledku

19

Strana od-do

923-941

Kód UT WoS článku

000397335700002

EID výsledku v databázi Scopus

2-s2.0-85013498051