This content has been automatically translated from Ukrainian.
NP-complexity this is a class of problems for which it is very difficult to find a solution, but it is easy to check the correctness of the already finished one. In other words, if you guessed the answer, you can check it quickly, but the search process itself takes an extremely long time.
Examples of NP-hard problems:
- Salesman's task - how to find the shortest route that passes through all cities.
- Class schedule - draw up an optimal schedule so that all teachers, classrooms and students coincide without conflicts.
- Subsets - divide the set of numbers into groups with the same sum.
Where it matters in real life:
- Logistics and delivery routes.
- Production planning and schedules.
- Cryptography and data security.
A simple Ruby example for demonstrating the idea of a complete search (on the example of subsets):
# NP-hard problem: finding a subset with the desired sum
numbers = [3, 7, 9, 11, 15]
target = 20
solutions = []
(1..numbers.size).each do |k|
numbers.combination(k).each do |subset|
solutions << subset if subset.sum == target
end
end
puts "Solutions Found:"
solutions.each { |s| ps}
Result:
Solutions found: [9, 11]
Several options are visible here. And if you increase the array to 20–25 numbers, the number of checks will increase sharply - that's what it looks like combinatorial explosion, whereby similar NP-hard problems become practically insoluble by an enumeration.
This post doesn't have any additions from the author yet.
