Кормена

Да и тема, совсем не talks.

http://en.m.wikipedia.org/wiki/Travelling_salesman_problem
Там есть ссылки на эвристики

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

Метод ветвей и границ.

Метод ветвей и границ

+1

Я в девятом классе писал курсач на эту тему, метод ветвей и границ порвал как тряпку мои потуги в генетических алгоритмах. Но это было давно и может я эти ГА неправильно готовил.

Эксплуатируй пчелу

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

Можете сказать чего читать?

ну я программировал на octave как-то генетический. Вроде на 30 работал неплохо.

вообще есть еще алгоритм, что с помощью Lagrange Relaxation работает. он дает хорошие результаты.

Игровые модели

А решить методами теории игр Вы не пробовали? Там же все прекрасно раскладывается на графы с последующим поиском пути.

Вы вообще знаете, что такое теория игр? И что в итоге она все равно сводится к оптимизации, классической или эвристической?

посмотри в «в мире науке»/scientific america была статья на тему эврестических решений np-полных задач ( которые сводимы друг к другу через полином)

так вот там был описан метод на мыльных плёнках(т.е использование законов физики и физического процесса как массово паралельного устройства ) для задачи как и где размещать перекрёстки и дороги для набора населённых пунктов - доказано что такая эвристика даёт дорожную сеть гарантированно не более чем в два раза длиннее оптимального - на вике то же про это есть

Гэри Джонсон название что то типо сложнорешаемые задачи.

Что? Полиномы? А? Мыльные плёнки? Свали, наркоман!

ты в курсе дааааааа?

была идея решать ее физ. процессом но не нашли пока подходящего

Короче, пока был найден, кроме генетического, 3-Opt.

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

Буду читать.

Слава тебе господи есть пара его книг в библиотеке.

Целочисленное линейное программирование. Как и почти все комбинаторные задачи:) Для начала можешь просто сделать релаксацию {0, 1} на [0, 1], и решить обычным солвером, после чего затрешолдить обратно в {0, 1}. Уже после этого пробуй забацать более точную аппроксимацию с помощью cutting planes и gomory's cuts. Советую именно так идти к branch and bounds.

Но если нужно чтобы просто работало, то просто найди специализированный солвер для целочисленного линейного программирования и используй его. К сожелению, многие качественные солверы платные. Посмотри в сторону CPLEX http://en.wikipedia.org/wiki/CPLEX или его суррогата http://en.wikipedia.org/wiki/GLPK . Затестить CPLEX можешь тут _http://www.ifor.math.ethz.ch/cplex/index.en.html

Ищи по integer linear programming, 0-1 linear programming, cutting planes.

И еще, очень советую держаться подальше от такого дерьма как «генетический алгоритм» :3

Я делаю это для учебы. Нам тоже сказали генетику не трогать, обосновав тем что для нее нужно делать большую популяцию и имеет смысл использовать только для большого количества городов.

Короче, спасибо.

Потом у меня на самом деле Sequential ordering problem. Гы гы.