Обсуждение:Задача коммивояжера, ДП по подмножествам — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «* Немного подробнее раскрыть тему NP-полных задач.»)
 
 
(не показано 8 промежуточных версий этого же участника)
Строка 1: Строка 1:
* Немного подробнее раскрыть тему NP-полных задач.
+
: {{tick | ticked=1}} В конспекте написано что задача отностится к классу NP-полных, но не сказано что это такое. Объяснить кратко.
 +
: {{tick | ticked=1}} Написать (псевдо)код.
 +
: {{tick | ticked=1}} Оформить три условия dp[i][m] нормально, как динамику — то есть база и переход. Использовать теховские большие фигурные скобки(для условного присваивания)(как здесь [[Задача о перемножении матриц#Рекурсивное решение]])
 +
: {{tick | ticked=1}} дополнительные улучшения форматирования приветствуются --[[Участник:Dgerasimov|Дмитрий Герасимов]]
 +
 
 +
 
 +
: {{tick | ticked=1}} Пункт «Формулировка задачи» не нужен, то что в нём можно поместить в шапку статьи.
 +
: {{tick | ticked=1}} Сложность решения методом перебора перестановок посчитана неправильно — у тебя N! перестановок и N времени на подсчёт длины каждого пути.
 +
: {{tick | ticked=1}} Используется то <tex> s </tex>, то <tex> S </tex>
 +
: {{tick | ticked=1}} То, что должно быть под <tex> \min </tex> почему-то справа. Видимо, надо использовать \limits.
 +
: {{tick | ticked=1}} «т.е. mask - подмножество вершин исходного графа, которые осталось посетить» — непонятно, какие именно вершины в mask осталось посетить. В общем, строго напиши, что обозначает 0 и что — 1.
 +
: {{tick | ticked=1}} Мне кажется, у тебя неправильно задана динамика(или описание у неё неправильное). d[i=0][mask=0] — конечное состояние(как написано перед заданием динамики), а значение в нём у тебя задаётся равным нулю. И вообще у тебя текстовое описание и до и после описания динамики формулами, определись.
 +
: {{tick | ticked=1}} В псевдокоде здесь писать 2 ^ j — плохо, так как «^» — xor. Пиши с битовым сдвигом или хотя бы 2 ** j.
 +
: {{tick | ticked=1}} В псевдокоде d[i][mask] = min(d[i][mask], d[j][mask - 2 ^ j]);, а надо d[i][mask] = min(d[i][mask], d[j][mask - 2 ^ j] + вес ребра(не знаю как он у тебя там называется);
 +
: {{tick | ticked=1}} Писать inputData и writeData не обязательно. Лучше оформить в виде функции, которая принимает то что нужно для того, чтобы решать задачу и возвращает d[0][2 ** n - 1]
 +
: {{tick | ticked=1}} А ещё не очень понятно, почему весовая функция для рёбер обознается p. Я понимаю, w(weight) или e(edges) или ещё что-то, имеющее аналог в английском языке.
 +
--[[Участник:Dgerasimov|Дмитрий Герасимов]] 00:46, 2 декабря 2011 (MSK)
 +
 
 +
== Замечания АС ==
 +
: {{tick | ticked=1}} Неверная постановка задачи: почему на плоскости? Сами бы почитали википедию, на которую ссылаетесь!
 +
:: Все равно выглядит трешово. Я бы вообще сформулировал задачу в терминах графов. Тем более, ты в конспекте пользуешься ими. --[[Участник:Dgerasimov|Дмитрий Герасимов]] 04:35, 13 января 2012 (MSK)
 +
: {{tick | ticked=1}} "Так вот задача о коммивояжере относится к классу NP-полных задач. Рассмотрим два варианта решения. " Тут не хватает мотивирующей связки между этими предложениями. Типа "Поэтому, рассмотрим два варианта решения с экспоненциальным временем работы"
 +
: {{tick | ticked=1}} Не умеете писать русскими буквами в формулах? \text{} вас (возможно) спасет
 +
:: {{tick | ticked=1}} стало нифига не понятно условие после бесконечности в большой фигурной скобке.

Текущая версия на 08:05, 29 февраля 2012

В конспекте написано что задача отностится к классу NP-полных, но не сказано что это такое. Объяснить кратко.
Написать (псевдо)код.
Оформить три условия dp[i][m] нормально, как динамику — то есть база и переход. Использовать теховские большие фигурные скобки(для условного присваивания)(как здесь Задача о перемножении матриц#Рекурсивное решение)
дополнительные улучшения форматирования приветствуются --Дмитрий Герасимов


Пункт «Формулировка задачи» не нужен, то что в нём можно поместить в шапку статьи.
Сложность решения методом перебора перестановок посчитана неправильно — у тебя N! перестановок и N времени на подсчёт длины каждого пути.
Используется то [math] s [/math], то [math] S [/math]
То, что должно быть под [math] \min [/math] почему-то справа. Видимо, надо использовать \limits.
«т.е. mask - подмножество вершин исходного графа, которые осталось посетить» — непонятно, какие именно вершины в mask осталось посетить. В общем, строго напиши, что обозначает 0 и что — 1.
Мне кажется, у тебя неправильно задана динамика(или описание у неё неправильное). d[i=0][mask=0] — конечное состояние(как написано перед заданием динамики), а значение в нём у тебя задаётся равным нулю. И вообще у тебя текстовое описание и до и после описания динамики формулами, определись.
В псевдокоде здесь писать 2 ^ j — плохо, так как «^» — xor. Пиши с битовым сдвигом или хотя бы 2 ** j.
В псевдокоде d[i][mask] = min(d[i][mask], d[j][mask - 2 ^ j]);, а надо d[i][mask] = min(d[i][mask], d[j][mask - 2 ^ j] + вес ребра(не знаю как он у тебя там называется);
Писать inputData и writeData не обязательно. Лучше оформить в виде функции, которая принимает то что нужно для того, чтобы решать задачу и возвращает d[0][2 ** n - 1]
А ещё не очень понятно, почему весовая функция для рёбер обознается p. Я понимаю, w(weight) или e(edges) или ещё что-то, имеющее аналог в английском языке.

--Дмитрий Герасимов 00:46, 2 декабря 2011 (MSK)

Замечания АС

Неверная постановка задачи: почему на плоскости? Сами бы почитали википедию, на которую ссылаетесь!
Все равно выглядит трешово. Я бы вообще сформулировал задачу в терминах графов. Тем более, ты в конспекте пользуешься ими. --Дмитрий Герасимов 04:35, 13 января 2012 (MSK)
"Так вот задача о коммивояжере относится к классу NP-полных задач. Рассмотрим два варианта решения. " Тут не хватает мотивирующей связки между этими предложениями. Типа "Поэтому, рассмотрим два варианта решения с экспоненциальным временем работы"
Не умеете писать русскими буквами в формулах? \text{} вас (возможно) спасет
стало нифига не понятно условие после бесконечности в большой фигурной скобке.