Wyniki wyszukiwania - BazTech

1

Comparing Problem Solving Strategies for NP-hard Optimization Problems

Hidalgo-Herrero M., Rabanal P., Rodríguez I., Rubio F.

Fundamenta Informaticae

|

2013

|

Vol. 124, nr 1/2

1--25

EN

NP-complete problems are particularly hard to solve. Unless P=NP, any algorithm solving an NP-complete problem takes exponential time in the worst case. The intrinsic difficulty of NP-complete problems when we try to optimally solve them with computers seems to apply to humans too. Intuitively, solving NP-complete problems requires taking a series of choices where each choice we take disables many subsequent choices, but the scope of dependencies between these mutually exclusive choices cannot be bound. Thus, the problem cannot be split into smaller subproblems in such a way that their solutions can be computed independently and easily combined for constructing the global solution (as it happens in divide and conquer algorithms). Moreover, for each choice, the space of subsequent subproblems to be considered for all possible choice elections does not collapse into a polynomial size set (as it happens in dynamic programming algorithms). Thus, intuitively, in NP-complete problems any choice may unboundedly affect any other, and this difficulty seems to puzzle humans as much as computers. In this paper we conduct an experiment to systematically analyze the performance of humans when solving NP-complete problems. For each problem, in order to measure partial fulfillment of the decision problem goal, we consider its NP-hard optimization version. We analyze the human capability to compute good suboptimal solutions to these problems, we try to identify the kind of problem instances which make humans compute the best and worst solutions (including the dependance of their performance on the size of problem instances), and we compare their performance with computational heuristics typically used to approximately solve these problems. We also interview experiment participants in order to infer the most typical strategies used by them in experiments, as well as how these strategies depend on the form and size of problem instances.

2

Shortest path problem solving based on ant colony optimization metaheuristic

Głąbowski M., Musznicki B, Nowak P., Zwierzykowski P.

Image Processing & Communications

|

2012

|

Vol. 17, no. 1-2

7--17

EN

The Ant Colony Optimization (ACO) metaheuristic is a versatile algorithmic optimization approach based on the observation of the behaviour of ants. As a result of numerous analyses, ACO has been applied to solving various combinatorial problems. The ant colony metaheuristic proves itsel I' to be efficient in solving NP-hard problems, often generating the best solution in the shortest amount of time. However, not enough attention has been paid to ACO as a means of solving problems that have optimal solutions which can be found using other methods. The shortest path problem is undoubtedly one of the aspects of great significance to navigation and telecommunications. It is used, amongst others, for determining the shortest route between two geographical locations, for routing in packet networks, and to balance and optimize network utilization. Thus, this article introduces ShortestPathACO, an Ant Colony Optimization based algorithm designed to find the shortest path in a graph. The algorithm consists of several subproblems that are presented successively. Each subproblem is discussed from many points of view to enable researchers to find the most suitable solutions to the problems they investigate.

3

Rozproszony przegląd zupełny z obcięciami w drzewie poszukiwań dla problemów NP-trudnych

Tusiewicz M.

Automatyka / Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie

|

2005

|

T. 9, z. 1-2

245-253

PL

Artykuł przedstawia zagadnienie znajdowania optimum problemów NP-trudnych w środowiskach rozproszonych złożonych z dużej liczby maszyn, połączonych w luźno powiązane podsieci. Całość omawiana jest na podstawie optymalizacyjnego, dyskretnego problemu plecakowego rozwiązywanego za pomocą przeglądu zupełnego zmodyfikowanego o dokonywanie obcięć w drzewie poszukiwań. Do scharakteryzowania problemu oraz przedstawienia algorytmu użyto modelu środowiska rozproszonego zaproponowanego przez autora.

EN

Optimum finding of NP-hard problems in wide distributed environments algorithm is presented. As an main example 0—1 Knapsack Problem is solved using distributed complete search with branch-and-bound technique. Distributed environment model proposed by the author is used to describe the algorithm and efficiency estimations.

4

Optimal resource allocation for single machine scheduling problems with time and resource dependent processing times.

Iwanowski D., Janiak A.

Systems Science

|

2002

|

Vol. 28, nr 2

85-94

EN

The paper is devoted to the single machine scheduling problems with time and resource dependent processing times. The following criteria are considered: the makespan and the total completion time subject to a given constraint on the total resource consumption and the total resource consumption criterion subject to a given constraint either on the makespan or on the total completion time, respectively. The problems are mostly NP-hard. The solution of such a kind of scheduling problem contains the permutation describing the optimal sequence of jobs and the optimal resource allocation vector. In general, there is no possibility to find the optimal sequence of jobs and the optimal resource allocation separately. Usually, the resource allocation depends on the sequence of jobs and the sequence depends on the resource allocation. Despite of that fact, in some particular applications the methods of an optimal resource allocation vector construction for a given arbitrary sequence of jobs may be very useful. For instance, such methods are necessary to construct some heuristic algorithms. Our interest was to find and describe these methods. We proved that they operate in polynomial time.