Недавно добавленные исходники

•  3D Designer  433

•  Sik Screen Capture  309

•  Patch Maker  269

•  Айболит (remote control)  341

•  ListBox Drag & Drop  247

•  Доска для игры Реверси  4 724

•  Графические эффекты  297

•  Рисование по маске  229

•  Перетаскивание изображений  249

•  Canvas Drawing  265

•  Рисование Луны  252

•  Поворот изображения  145

•  Рисование стержней  144

•  Paint on Shape  109

•  Генератор кроссвордов  148

•  Головоломка Paletto  142

•  Теорема Монжа об окружностях  175

•  Пазл Numbrix  102

•  Заборы и коммивояжеры  183

•  Игра HIP  123

 

 

Архив исходников

   
  Базы данных
  Графика & Мультимедиа
  Сети & Интернет
  Система
  Разное
   

Ссылки и Баннеры ...

 

Delphi Sources

Delphi Sources

 




 

ИСХОДНИК ПРОГРАММЫ

 

. : Задача коммивояжера : .

 

Delphi - Задача коммивояжера требует, чтобы мы нашли кратчайший путь, посетив каждый из заданного набора городов и вернулись в исходную точку

Исходник программы, показывающей пример решения задачи коммивояжера, которая требует, чтобы мы нашли кратчайший путь, посетив каждый из заданного набора городов и вернулись в исходную точку.

TSP относится к классу задач, которые по какой-то неочевидной причине называются NP-полными. У этих проблем нет известных эффективных алгоритмов их решения. «Неэффективно» здесь означает, что время решения проблемы увеличивается экспоненциально с увеличением размера проблемы, т.е. время решения - это выражение, которое содержит N в качестве показателя степени. Это намного более быстрый темп роста, чем любая задача с полиномиальным временем (сравните значения N2 и 2N для N = 2, 10, 20 и 30, чтобы увидеть эффект экспоненциального роста в простейшем случае).

Похоже, что в настоящее время ведется много исследований эффективных методов решения TSP - первое решение для 15 000 городов было найдено только в 2001 году, что значительно больше по сравнению с знаменательным решением для 49 городов, найденным в 1954 году. Есть и другие приложения TSP, например: проблемы с роботами, такие как пайка или сверление на печатных платах, определение последовательности локальных карт генома для создания глобальной карты, планирование порядка, в котором спутниковый интерферометр изучает последовательность звезд и т.д. Возможно, так же важно, как и прямые приложения, TSP обеспечивает основу для академических исследований проблем дискретной оптимизации. Определенно интригует то, что проблему, которую так легко сформулировать, может быть так сложно решить.

Исчерпывающий поиск разбивается примерно на 15 городов (около триллиона, 1012 путей для проверки). Когда количество городов превысит число подростков, нам придется полагаться на эвристические методы (практическое правило), которые обеспечивают «довольно хорошие» или «достаточно хорошие» решения.

Эта программа показывает карту 48 смежных штатов США и позволяет вам сгенерировать набор из 50 городов и щелкнуть по ним, чтобы сформировать путь с вашим общим пробегом. Для компьютерного поиска пути предусмотрены как кнопки исчерпывающего поиска, так и кнопки эвристических методов.

Просмотры: 169
Дата: 08.07.2021, Автор: Gary Darby
Написать сообщение:
 

 

Скачать (159 Кб)   ↓ 3   Регистрация >>


 

Похожие исходники


Задача «Иосифа Флавия»

 

© 2004-2021 "DS"

Соглашение пользователя / Реклама / Карта сайта             Created by BrokenByte Software