Компьютерный форум
Правила
Вернуться   Компьютерный форум > Форум программистов > Языки программирования > Prolog
Перезагрузить страницу 25 задач по Прологу к экзамену
Ответ
 
Опции темы Опции просмотра
  (#46 (permalink)) Старый
Alison Alison вне форума
Member
 
Сообщений: 4,771
Сказал(а) спасибо: 0
Поблагодарили 119 раз(а) в 116 сообщениях
Регистрация: 17.11.2004
По умолчанию 12.09.2006, 20:58

Насчет конференции не преувеличивай. Понять что-либо в рамках короткого доклада в принципе невозможно. Да, твоя прямоугольная раскладка производит большое впечатление.
Но общий метод, естественно, не мог быть продемонстрирован, и примеров решения задачи про сдачу и других из вышеперечисленных, не было.
И твой метод не был описан как метод решения какого-либо класса NP-полных задач (это и невозможно все сделать в рамках одного доклада).
Что касается решения таких задач, основную проблему я вижу именно в порождении приближенных решений, больше, чем в выборе из них наилучшего.
О том, как с помощью ранжированного дерева поиска, можно находить оптимальные пути на графе, также речи не было (в задаче про раскладку, которую ты демонстрировал, графов нет).

И потом, проблему для тебя я вижу не в практике, а в теории (моделировании).
(насчет факториалов - их использование здесь совершенно лишнее)
Причем здесь опять вероятные и невероятные решения? Разве ты используешь на практике случайный выбор?
Решения у тебя порождаются с помощью экспертных правил, вполне опеределенным образом. Теория вероятностей здесь ни при чем, и разумную модель с ее помощью ты вряд ли построишь. С помощью статистики ты находишь среди готовых решений лучшее. Но ты не используешь эвристики, полученные с помощью статистики, для порождения вариантов решений. Полные графы тоже в модели, например, для задачи про сдачу (я не знаю про остальные, т.к. ты ничего о них не писал), тоже не должны возникать. Не нужно рассматривать модели, "сложнее", чем полный перебор (в данном случае это именно сочетания с повторениями). Ведь на практике у тебя ничего такого нет! Так и в моделях ничего этого не должно быть. Модель должна отражать то, что есть. Они строятся обычно для того, чтобы улучшить ситуацию и прояснить ее, а не затуманить.
Ответить с цитированием
  (#47 (permalink)) Старый
Винитарх Винитарх вне форума
Специалист
 
Аватар для Винитарх
 
Сообщений: 7,910
Сказал(а) спасибо: 2
Поблагодарили 297 раз(а) в 297 сообщениях
Регистрация: 01.03.2003
Адрес: Краснодар
По умолчанию 14.09.2006, 18:25

Цитата:
О том, как с помощью ранжированного дерева поиска, можно находить оптимальные пути на графе, также речи не было (в задаче про раскладку, которую ты демонстрировал, графов нет).
На конференции пол доклада было этому посвящено. Раскладуха и вообще любая NP-трудная задача - это графы, графы, графы... В такой простой задаче, как задача про сдачу, граф пустой, но он легко делается полным для целей ранжирования дерева поиска. И если по нормальному, то задачу про сдачу надо решать в более реальной постановке, где даются не только номиналы монет, но и количество монет для каждого номинала. Монеты - это ресурсы, которые должны расходоваться, иначе задача становится столь абстрактной, что к практике её не приложить.

Цитата:
насчет факториалов - их использование здесь совершенно лишнее
Именно в факториальной системе счисления (ФСС) я и нумерую/перечисляю варианты решений, и выражаю эвристики для различных типов упорядочивания вариантов.

Цитата:
Причем здесь опять вероятные и невероятные решения? Разве ты используешь на практике случайный выбор?
На практике я не использую случайный выбор напрямую. На практике я использую эвристики, которые построены на основе статистики, в природу которой положена вероятность оптимальности каждого решения. А решение представлено в факториальной системе счиления.

Цитата:
Решения у тебя порождаются с помощью экспертных правил, вполне опеределенным образом. Теория вероятностей здесь ни при чем, и разумную модель с ее помощью ты вряд ли построишь.
Просмотр вариантов решений у меня упорядочивается с помощью СТАТИСТИЧЕСКИ ОБОСНОВАННЫХ эвристик. О каждом конкретном решении я АПРИОРИ знаю какова вероятность того, что это решение оптимальное. Поэтому и могу упорядочить все решения.

Цитата:
С помощью статистики ты находишь среди готовых решений лучшее.
Нет. С помощью эвристик я упорядочиваю просмотр НЕготовых решений. Упорядочение - априорное. Каждое решение имеет свой номер в факториальной системе счисления. Вот по коэффициентам этой ФСС я и веду упорядочивание.

Цитата:
Но ты не используешь эвристики, полученные с помощью статистики, для порождения вариантов решений.
Именно для ЭТОГО (для порождения вариантов решений) я и использую эвристики, т.к. эвристики у меня СТАТИСТИЧЕСКИ (и уже аналитически) ОБОСНОВАНЫ. Я два года гонял NP-трудные задачи на графах. У меня комп выключался только на ночь. Пол винта забито таблицами и графиками со средними значениями и дисперсиями.

Цитата:
Полные графы тоже в модели, например, для задачи про сдачу (я не знаю про остальные, т.к. ты ничего о них не писал), тоже не должны возникать.
Полный граф - это теоретически полная модель всех ситуаций. Для большинства NP-трудных задач наличие перестановок очень важно, т.к. перестановки дают разные значения целевой функции. Для задачи про сдачу перестановки, конечно, являются лишними, но они совершенно не опровергают использование предлагаемого подхода к упорядочиванию решений NP-трудных задач.

Цитата:
Не нужно рассматривать модели, "сложнее", чем полный перебор (в данном случае это именно сочетания с повторениями). Ведь на практике у тебя ничего такого нет!
В задаче про сдачу этого нет. В НАСТОЯЩИХ практических задачах это есть.

Цитата:
Модель должна отражать то, что есть. Они строятся обычно для того, чтобы улучшить ситуацию и прояснить ее, а не затуманить.
Нет. Модели строятся не для этого. Модели строятся на основе гомоморфизма для того чтобы упростить ситуацию за счёт введения различных допущений. Изоморфных моделей на практике не бывает.
Для задачи про сдачу никакой модели строить не надо, т.к. эта задача в своей постановке не имеет и не отражает какую-либо предметную область, и в которой параметров столь много, что несущественные для задачи параметры можно отбросить или упростить.
Ответить с цитированием
  (#48 (permalink)) Старый
Alison Alison вне форума
Member
 
Сообщений: 4,771
Сказал(а) спасибо: 0
Поблагодарили 119 раз(а) в 116 сообщениях
Регистрация: 17.11.2004
По умолчанию 14.09.2006, 20:37

На доклад относительно "теории" лучше пока не ссылаться.
Цитата:
Раскладуха и вообще любая NP-трудная задача - это графы, графы, графы... В такой простой задаче, как задача про сдачу, граф пустой, но он легко делается полным для целей ранжирования дерева поиска. И если по нормальному, то задачу про сдачу надо решать в более реальной постановке, где даются не только номиналы монет, но и количество монет для каждого номинала.
Приведи, пожалуйста, конкретный пример, для конкретной задачи про сдачу, как у тебя появляется полный граф. Это совсем непонятный момент.
Цитата:
Именно в факториальной системе счисления (ФСС) я и нумерую/перечисляю варианты решений, и выражаю эвристики для различных типов упорядочивания вариантов.
Но почему? Тебе нужны только коэффициенты при факториалах, каково обоснование появления самих факториалов? Это не выглядит убедительно.
Цитата:
О каждом конкретном решении я АПРИОРИ знаю какова вероятность того, что это решение оптимальное.
Что ты называешь решением? Что ты называешь приближенным решением? И вообще, в каком вероятностном пространстве? В пространстве всех приближенных решений? Или в пространстве полученных тобой решений (думаю, что они совпадают)? Или в другом каком-либо?
Вероятность того, что решение на самом деле оптимальное или вероятность того, что оно наилучшее из заданного набора?
Ты получил некоторый набор приближенных решений. Далее ты по своим критерям выбираешь из них лучшее. При чем здесь вероятность?
Попробуй приведи пример, для сдачи 88 и монет {27, 21, 5, 3} или для более простой задачи про сдачу.
Цитата:
Каждое решение имеет свой номер в факториальной системе счисления. Вот по коэффициентам этой ФСС я и веду упорядочивание.
Непонятно, при чем тут ФСС (например, даже в задаче про раскладку). Ты не можешь взять просто набор коэффициентов? А факториалы, например, в задаче про сдачу, непонятно, откуда могут взяться.
Если считать, что на каждом шаге можно брать любую монету, т.е. на каждом шаге возможностей n, то всего вариантов решений n^N, где N - число сделанных шагов.
Цитата:
Пол винта забито таблицами и графиками со средними значениями и дисперсиями.
Средние значения чего? и т.д. Поподробнее можно?
Цитата:
Полный граф - это теоретически полная модель всех ситуаций.
Опиши, пожалуйста, полный граф на маленьком примере. Что есть вершины, а что ребра? Откуда он берется? Что является ситуацией?
Цитата:
Модели строятся на основе гомоморфизма для того чтобы упростить ситуацию за счёт введения различных допущений. Изоморфных моделей на практике не бывает.
Именно упростить.
А насчет изоморфизма - смотря чего модель и смотря какая модель.
И вообще, я имела в виду описание того, что ты уже реально сделал, сделал на практике.
Ответить с цитированием
Ads
  (#49 (permalink)) Старый
Винитарх Винитарх вне форума
Специалист
 
Аватар для Винитарх
 
Сообщений: 7,910
Сказал(а) спасибо: 2
Поблагодарили 297 раз(а) в 297 сообщениях
Регистрация: 01.03.2003
Адрес: Краснодар
По умолчанию 16.09.2006, 20:54

Цитата:
Приведи конкретный пример, для конкретной задачи про сдачу, как у тебя появляется полный граф. И опиши подробно сам полный граф.
Очень вкратце.
Каждая вершина графа - одна монета. Вес вершины (действительное число) - номинал монеты. Каждый номинал представлен в единичном экземпляре (это не принципиальное ограничение). Все вершины связаны между собой рёбрами. Рёбра, инцидентные произвольной вершине, проранжированы (начиная с нуля) в соответствии с весом вершин, принадлежащих окрестности этой произвольной вершины. Выбираемые монеты удаляются из графа вместе с инцидентными рёбрами. Одновременно с этим выбираемые монеты собираются в цепь (практически - проложный список) вершин. Сумма весов вершин цепи является весом цепи (текущей сдачей).
Задача №1 - найти цепь с весом, наиболее близким к сдаче (т.е. минимизировать или абсолютное значение ошибки, или справа, или слева).
Задача №2 - найти цепь минимальной длины с заданным весом (сдача), если таковая существует.
Из этих двух задач я опробовал свою методу только на задаче №1 - резка проволоки, труб, ленты, сетки Рабица и прочих одномерных материалов с минимизацией непромышленных остатков. Задачу №2 я не рассматривал ввиду отсутствия, на мой взгляд, её практического приложения.
С "высоты" этой задачи может показаться, что понятие цепи здесь излишне. Но это на самом деле не так. Я повторюсь, метод перебора - общий, и распространяется на все NP-задачи, связанные с расходованием чего-либо (в данном случае - монет). В большинстве таких задач понятие цепи необходимо, т.к. перестановки СУЩЕСТВЕННЫ (не хочу вдаваться здесь в причины этой необходимости).

Если в этих цепях вершины заменить на ранг ребра, которое "привело" к выбору этой вершины, то мы получим ранжированные цепи - одновременно инструмент и объект исследования. Если была выбрана наибольшая к оставшейся сдаче монета, то её ранг = 0 (Беллмановская монета). Если вторая после наибольшей - ранг = 1, и т.д.

Пример ранжированных цепей:
[0,0,0] - выбор трёх Беллмановских монет.
[1,2,0] - выбор первой монеты на один номинал хуже "Беллмановской", потом выбор второй монеты на два номинала хуже "Беллмановской", потом выбор третьей монеты - собственно "Беллмановской" монеты.

Пример статистики (привожу примерно десятую часть статистики, но и на ней видно куда дело идёт).
Количество испытаний = 30000.
Число монет = 10.
Значение сдачи при испытаниях определялась как полова суммы весов всех вершин (однако это тоже не принципиально для нахождения статистических эвристик).
Эффект(ивность) - это отношение ошибки к значению сдачи, для нашй беседы этот параметр не нужен, но мне влом прыгать мышкой и стирать.
Перед каждым испытанием номиналы монет и сдача генерились заново случайным образом, по моему - из диапазона [0,1].

Код:
Ранж.цепь = [0,0]         Эффект = 0.979050791    Число_побед = 2397
Ранж.цепь = [1,0]         Эффект = 0.9793944934   Число_побед = 2017
Ранж.цепь = [2,0]         Эффект = 0.9759674282   Число_побед = 1805
Ранж.цепь = [3,0]         Эффект = 0.9373095147   Число_побед = 684
Ранж.цепь = [4,0]         Эффект = 0.8371390834   Число_побед = 18
Ранж.цепь = [5,0]         Эффект = 0.8111093794   Число_побед = 0
Ранж.цепь = [0,1,0]       Эффект = 0.9790914533   Число_побед = 2100
Ранж.цепь = [0,2,0]       Эффект = 0.9773942874   Число_побед = 1900
Ранж.цепь = [0,3,0]       Эффект = 0.9721473244   Число_побед = 1422
Ранж.цепь = [0,4,0]       Эффект = 0.9057560462   Число_побед = 181
Ранж.цепь = [0,5,0]       Эффект = 0.8466096582   Число_побед = 1
Ранж.цепь = [0,6,0]       Эффект = 0.8946859843   Число_побед = 0
Ранж.цепь = [1,1,0]       Эффект = 0.9764578848   Число_побед = 1701
Ранж.цепь = [1,2,0]       Эффект = 0.9670152043   Число_побед = 1099
Ранж.цепь = [1,3,0]       Эффект = 0.8852730504   Число_побед = 73
Ранж.цепь = [1,4,0]       Эффект = 0.8338423414   Число_побед = 0
Ранж.цепь = [2,1,0]       Эффект = 0.9566738323   Число_побед = 828
Ранж.цепь = [2,2,0]       Эффект = 0.8709292111   Число_побед = 39
Ранж.цепь = [2,3,0]       Эффект = 0.8274573389   Число_побед = 0
Ранж.цепь = [3,1,0]       Эффект = 0.8619656244   Число_побед = 33
Ранж.цепь = [3,2,0]       Эффект = 0.8246267639   Число_побед = 0
Ранж.цепь = [4,1,0]       Эффект = 0.8223464142   Число_побед = 0
Ранж.цепь = [0,0,1,0]     Эффект = 0.9775226063   Число_побед = 1547
Ранж.цепь = [0,0,2,0]     Эффект = 0.9749915013   Число_побед = 1238
Ранж.цепь = [0,0,3,0]     Эффект = 0.969526185    Число_побед = 996
Ранж.цепь = [0,0,4,0]     Эффект = 0.9623439818   Число_побед = 509
Ранж.цепь = [0,0,5,0]     Эффект = 0.9095652403   Число_побед = 32
Ранж.цепь = [0,0,6,0]     Эффект = 0.8879996275   Число_побед = 0
Тенденция видна невооружённым глазом. Это нам даёт право априорно указать такой порядок посмотра, при котором будут просматриваться сначала наиболее вероятные кандидаты в победители, т.е.:
Код:
Ранж.цепь = [0,0]         Эффект = 0.979050791    Число_побед = 2397
Ранж.цепь = [0,1,0]       Эффект = 0.9790914533   Число_побед = 2100
Ранж.цепь = [1,0]         Эффект = 0.9793944934   Число_побед = 2017
Ранж.цепь = [0,2,0]       Эффект = 0.9773942874   Число_побед = 1900
Ранж.цепь = [2,0]         Эффект = 0.9759674282   Число_побед = 1805
Ранж.цепь = [1,1,0]       Эффект = 0.9764578848   Число_побед = 1701
Ранж.цепь = [0,0,1,0]     Эффект = 0.9775226063   Число_побед = 1547
и т.д.
Теперь можно "бездумно" проверить пару десятков самых вероятных цепей (первые семь указаны выше) и выбрать лучшую. Результат будет потрясающий! Вот такие вот делы.
Ранги цепей есть не что иное как коэффициенты ФСС, в которой можно легко описать закон упорядочивания цепей для любого числа монет, для любой сдачи и любого случайного закона генерации номиналов монет.
Также, ФСС нужна для оценки вычислительных затрат алгоритма и сравнения различных упорядочивающих эвристик между собой.

Искренне Ваш, Винитархъ.
Ответить с цитированием
  (#50 (permalink)) Старый
Alison Alison вне форума
Member
 
Сообщений: 4,771
Сказал(а) спасибо: 0
Поблагодарили 119 раз(а) в 116 сообщениях
Регистрация: 17.11.2004
По умолчанию 17.09.2006, 12:14

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

Маленькое замечание.
1. Для того чтобы изобразить исходный набор монет в виде вершин полного графа, и затем изымать их оттуда, количество монет каждого номинала в исходном наборе, видимо, должно быть задано (сколько монет каждого номинала - столько вершин для каждой монеты).
Т.е. полный граф используется для изображения исходного набора монет, затем из него поочередно удаляются выбранные монеты (насколько я понимаю, для реальной задачи с большим количеством монет полный граф - воображаемый, в "компьютере" его нет). А после того, как прибл. решение будет найдено, можно вернуться к исходному графу из монет и прорисовать там его.

2. Раз взятая монетка удаляется из графа, то на очередном шаге нельзя брать вообще любую монету, а только любую монету из оставшихся.

3. Можно провести сравнение с лексикографическим порядком на множестве прибл. решений - слов в алфавите из номиналов монет, пример приведен немного выше на этой странице, в сообщении 42 (ассоциации возникают).

А насчет ФСС - пока ничего не видно.
Ответить с цитированием
Ads.
  (#51 (permalink)) Старый
Винитарх Винитарх вне форума
Специалист
 
Аватар для Винитарх
 
Сообщений: 7,910
Сказал(а) спасибо: 2
Поблагодарили 297 раз(а) в 297 сообщениях
Регистрация: 01.03.2003
Адрес: Краснодар
По умолчанию 17.09.2006, 17:32

Цитата:
Маленькое замечание.
Это скорее не замечания, а твоё домысливание того, чего я явно не описал в своём последнем посте. Правда кое с чем в твоих "замечаниях" я не согласен.

Цитата:
количество монет каждого номинала в исходном наборе, видимо, должно быть задано
Конечно. Я же писал: "Каждая вершина графа - одна монета." Однако это не принципиально. Можно сделать так: "одна вершина - один номинал".

Цитата:
насколько я понимаю, для реальной задачи с большим количеством монет полный граф - воображаемый, в "компьютере" его нет
В компьютере он есть, но только при исследовании задачи, а задача исследуется на малых графах: до 10-16 вершин. А при эксплуатации готовых эвристик графа конечно нет, есть только цепи, получаемые по эвристикам. На практике я проверял эвристики на 200 разных монетах. Больше не пробовал, но, думаю, что легко можно получить приближённое решение для сколь угодно большого графа, главное, чтоб памяти компа хватило.
Например, аналогичный подход я применил в задаче Гамильтонова цикла, пути и т.д. Я приближённо находил Гам.цикл и он был гораздо короче, чем циклы, получаемые спец.алгоритмами для Гам.цикла, например алгоритмами Рейтера и Ли.
Вообще эта задача на самом деле имеет мат.формулировку: "об оптимальном подмножестве заданного множества по критерию...". Поэтому о монетах и их номиналах можно уже не говорить, а говорить о числах подмножества и сумме чисел.

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

Цитата:
Раз взятая монетка удаляется из графа, то на очередном шаге нельзя брать вообще любую монету, а только любую монету из оставшихся.
Конечно! Иначе смысла в описанном мною удалении вершин-монет нет.

Цитата:
3. Можно провести сравнение с лексикографическим порядком на множестве прибл. решений - слов в алфавите из номиналов монет, пример приведен немного выше на этой странице, в сообщении 42 (ассоциации возникают).
Что ещё за сравнение? С чем сравнение? Ведь я же лексикографический порядок и привёл в своём последнем посте, только цепи вдобавок сгруппированы по длине. Причём у меня каждая цепь имеет свои стат.параметры: мат.ожидание, дисперсию и эффективность.
Короче, "все ходы подсчитаны" в прямом смысле этой фразы.

Цитата:
А насчет ФСС - пока ничего не видно.
"Не видно" наверое потому, что я КОНКРЕТНО не описал где и как я её использую.
1. ФСС я использую для оценки выч.сложности. и удельной выч.сложности (средние затраты для одной цепи).
2. ФСС я использую при построении и сравнении эвристик упорядочивания цепей по уменьшению мат.ожидания победы.
3. ФСС я использую в теории ранжированных цепей для совершения различных алгебраических операций при теоретическом исследовании свойств цепей, которые (свойства) определены практически.

Как ты считаешь, стоит ли выделить нашу беседу о монетах в отдельную тему?
Мне кажется, что стоит.
Ответить с цитированием
  (#52 (permalink)) Старый
Alison Alison вне форума
Member
 
Сообщений: 4,771
Сказал(а) спасибо: 0
Поблагодарили 119 раз(а) в 116 сообщениях
Регистрация: 17.11.2004
По умолчанию 18.09.2006, 21:11

Цитата:
Конечно. Я же писал: "Каждая вершина графа - одна монета." Однако это не принципиально. Можно сделать так: "одна вершина - один номинал".
Раз это не принципиально, то, может, и граф не сильно нужен? (это поверхностный взгляд со стороны, конечно, понятно, что графы ты используешь для предварительных исследований)
Цитата:
В компьютере он есть, но только при исследовании задачи, а задача исследуется на малых графах: до 10-16 вершин. А при эксплуатации готовых эвристик графа конечно нет,
Вот об этом и была речь. Т.е. для реальной задачи в компьютере графа все-таки нет (а прежде ты с этим все время спорил, если ты не будешь напускать туман, то тебе самому будет проще). Но, насколько я понимаю, и для задач на графах ты свой метод можешь применить.
Цитата:
Конечно! Иначе смысла в описанном мною удалении вершин-монет нет.
Но перед этим ты утверждал, что монета - любая, и никаких оговорок не было.
Понимаешь, когда ты неаккуратно выражаешь свои мысли, то понять тебя становится проблематичным.
Цитата:
Что ещё за сравнение? С чем сравнение? Ведь я же лексикографический порядок и привёл в своём последнем посте,
В сообщении 42 я привела пример для сдачи 88 и монет {27, 21, 5, 3}. Посмотри повыше.
Там я просто перечислила несколько первых слов (прибл. решений) в алфавите из номиналов монет. И почти сразу попала в оптимальное решение (это, конечно, не всегда так будет).
Так что эвристики очень нужны, и твои идеи, проверенные на практике, в частности, идея использовать лексикографический порядок, очень удачны.

Конечно, лексикографический порядок в силу природы этой задачи, наверное, самый естественный для нее.
А вообще, я думаю, что можно экспериментрировать с различными определениями расстояния между словами и в соответствии с ними - методами поиска приближенного решения.
Т.е. в принципе, можно просмотреть сначала прибл. решения, отстоящие "далеко" друг от друга, а потом просматривать некоторые окрестности некоторых прибл. решений относительно введенного расстояния (эти идеи тоже, в общем-то твои, но ты о них говорил как то иначе).
Цитата:
Причём у меня каждая цепь имеет свои стат.параметры: мат.ожидание, дисперсию и эффективность.
А как определяются мат. ожидание и дисперсия цепи?
Цитата:
...
3. ФСС я использую в теории ранжированных цепей для совершения различных алгебраических операций при теоретическом исследовании свойств цепей, которые (свойства) определены практически.
Определить-то, я думаю, операции можно. Но ведь главное - это обоснование.
Например, для задачи про сдачу перестановки не нужны, но метод работает. И ты пишешь, что для некоторых задач, где они важны, он тоже работает. Значит, нужно попытаться понять, почему он работает? От чего на самом деле это зависит? Наверное, в использовании ФСС здесь есть смысл, но это надо понять.
Цитата:
Как ты считаешь, стоит ли выделить нашу беседу о монетах в отдельную тему?
Мне кажется, что не стоит.
Если хочешь, тему можно просто переименовать (25 задач - это дело житейское). И потом, как-то так сложилось, что многие темы содержат отклонения в другую сторону. Так что это уже просто традиция.
Ответить с цитированием
  (#53 (permalink)) Старый
Alison Alison вне форума
Member
 
Сообщений: 4,771
Сказал(а) спасибо: 0
Поблагодарили 119 раз(а) в 116 сообщениях
Регистрация: 17.11.2004
По умолчанию 21.09.2006, 17:04

Если говорить серьезно, то тебя могут заинтересовать работы физиков (A. Sinclair и M. Jerrum) по применению методов цепей Маркова для оценки различных статистических характеристик комбинаторных конфигураций физических объектов (димеры и т.п.).

В руках комбинаториков (J.Propp, D.Wilson и др.) это превратилось в вероятностные схемы приближенного подсчета числа решений NP-полных задач (например, числа парасочетаний в двудольном графе). Это даже более сложные #P-полные задачи. Среди их методов есть вероятностный подход к поиску приближенных решений NP-полных задач (simulated anneling).

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

Математики, занимающиеся simulated anneling, для поиска субоптимального решения выбирают наилучшее из найденных с помощью цепей Маркова решений.
Ответить с цитированием
  (#54 (permalink)) Старый
Винитарх Винитарх вне форума
Специалист
 
Аватар для Винитарх
 
Сообщений: 7,910
Сказал(а) спасибо: 2
Поблагодарили 297 раз(а) в 297 сообщениях
Регистрация: 01.03.2003
Адрес: Краснодар
По умолчанию 21.09.2006, 18:57

Цитата:
Т.е. для реальной задачи в компьютере графа все-таки нет
Для задачи про монеты - нет. Для задач на графах - есть. => В общем случае - граф есть.

Цитата:
Но, насколько я понимаю, и для задач на графах ты свой метод можешь применить.
Конечно. Прежде всего на них, родных.

Цитата:
Но перед этим ты утверждал, что монета - любая, и никаких оговорок не было.
Правильно утверждал. Если нет ограничений на количество монет, то монета - любая.

Цитата:
Так что эвристики очень нужны, и твои идеи, проверенные на практике, в частности, идея использовать лексикографический порядок, очень удачны.
Всё с точносью до наоборот. Я против лексикографического перебора, т.к. он заведомо неоптимален. Пример этого я привёл выше в виде фрагмента стат.исследований задачи о сумму элементов подмножества. А для задач на графах лексикографический перебор по эффективности сродни случайному перебору, в общем - гадость.

Цитата:
эти идеи тоже, в общем-то твои, но ты о них говорил как то иначе
Да я о них вообще здесь не упоминал. Я нигде на форуме не привёл ни одной эвриситки - как надо перебирать варианты решений. Я просто показал как надо искать эвристики для этой задачи. А сами эвристики я пока приводить не буду, до поры до времени.

Цитата:
А как определяются мат. ожидание и дисперсия цепи?
Я использовал два показателя:
Показатель P1(i) является частотой наступления события, при котором вес цепи i минимален. Показатель P2(i) выражает математическое ожидание отношения веса hmin наилегчайшей цепи к весу цепи h(i).
Дисперсия для показателя P2 определяется обычным способом, без всяких хитростей.

Цитата:
Значит, нужно попытаться понять, почему он работает? От чего на самом деле это зависит?
Чего здесь пытаться то? Есть теоретическое обоснование, которое на 100% подтверждается опытом. Я его здесь не описывал, да и не буду до поры до времени.

Видишь ли - взболтнул я тут немного лишнего. Был нормальный разговор про задачу о монетах. Дак нет - влез я со своими идеями. И вот так всегда - влажу и начинаю раглагольствовать. Прекращать надо эти дела, ибо они немного расходятся с тем, что учат в ВУЗах.
Ответить с цитированием
  (#55 (permalink)) Старый
Винитарх Винитарх вне форума
Специалист
 
Аватар для Винитарх
 
Сообщений: 7,910
Сказал(а) спасибо: 2
Поблагодарили 297 раз(а) в 297 сообщениях
Регистрация: 01.03.2003
Адрес: Краснодар
По умолчанию 22.09.2006, 17:33

Цитата:
тебя могут заинтересовать работы физиков (A. Sinclair и M. Jerrum) по применению методов цепей Маркова
Цепи Маркова здесь не причём, т.к. налицо ПРИНЦИПИАЛЬНОЕ отличие между цепями Марокова и ранжированными цепями на дереве решений. В цепи Маркова каждое новое состояние является функцией только прежнего состояния и остальные прошлые состояния не играют рояли. В ранжированных цепях в общем случае новое состояние зависит от всей истории, т.е. от того, каким путём система попала в прежнее состояние. Это видно на тех задачах, где перестановки важны.

Цитата:
simulated anneling
Э. А при чём здесь симуляция отжига? Это вообще из другой оперы. Алгоритм отжига, генетический и муравьиный алгоритмы используют вероятностные схемы посторения (нахождения) решения. Я же в случае ранжированных цепей предлагаю не строить решение, а упорядочить их бесконечный перебор с возможностью останова в любой момент времени. Это даёт кучу достоинств, главное из которых - мы никогда не упадём в яму локального минимума.
Ответить с цитированием
  (#56 (permalink)) Старый
Alison Alison вне форума
Member
 
Сообщений: 4,771
Сказал(а) спасибо: 0
Поблагодарили 119 раз(а) в 116 сообщениях
Регистрация: 17.11.2004
По умолчанию 22.09.2006, 18:38

У тебя цепь - это одно прибл. решение (не знаю, полное или может быть и на какой-то стадии).
Цепь Маркова - это цепь прибл. решений.

Они с помощью цепей Маркова (вероятностными методами) находили прибл. решения NP-полных задач и более трудных (оценивали количество решений NP-полных задач).

Естественно, у тебя другое. У них давно все началось, поэтому есть известные работы, и в интернете тоже. Про твой способ ничего конкретного не известно, поэтому сравнивать что-либо и обсуждать невозможно в любом случае.
Ответить с цитированием
  (#57 (permalink)) Старый
Винитарх Винитарх вне форума
Специалист
 
Аватар для Винитарх
 
Сообщений: 7,910
Сказал(а) спасибо: 2
Поблагодарили 297 раз(а) в 297 сообщениях
Регистрация: 01.03.2003
Адрес: Краснодар
По умолчанию 25.09.2006, 23:04

Цитата:
У тебя цепь - это одно прибл. решение
Да. Но у меня идёт перебор сколь угодно большого количества цепей. И я могу остановиться на одной (лучшей цепи), а могу выбрать и несколько лучших цепей. Всё диктуется условиями конкретной задачи.

Цитата:
Про твой способ ничего конкретного не известно, поэтому сравнивать что-либо и обсуждать невозможно в любом случае.
Я опубликовал статейку о ранжированных цепях в журнале "Информационные технологии" за май этого года (я ж об этом говорил в самом начале). Правда написал её так, чтоб сторонний человек напрямую не воспользовался идеей, ибо я на ней бабки делаю. А кому надо - сам родит толковые эвристики при желании.
Ответить с цитированием
Ads
Ответ

Опции темы
Опции просмотра

Ваши права в разделе
Вы не можете создавать новые темы
Вы не можете отвечать в темах
Вы не можете прикреплять вложения
Вы не можете редактировать свои сообщения

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.
Trackbacks are Вкл.
Pingbacks are Вкл.
Refbacks are Выкл.


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
БИБЛИОТЕКА ПО ПРОЛОГУ!!! Винитарх Prolog 88 09.12.2015 01:58
Требуется помощь подготовка к экзамену ketti868 Pascal 1 24.06.2011 02:03
Где взять ответы на вопросы к экзамену по "Информационным системам"? NERO_1 Любые вопросы от новичков 11 12.02.2011 13:16
Контрольная по прологу Killer25m Prolog 0 23.11.2010 16:26
помогите допуститься к экзамену! sovsem_ novichok Prolog 0 14.07.2010 18:03
5 задач по прологу kotofey Prolog 14 31.05.2010 22:57
Пара задач по турбо прологу Midous Prolog 5 11.01.2010 13:08
три задачки по прологу imported_Жора Prolog 6 08.06.2007 00:34
лабы про прологу myrlogriz Prolog 4 02.11.2006 12:37
Тесты по Прологу IRINCHA Prolog 10 19.12.2005 15:25
задача по прологу dimants Prolog 1 07.11.2005 23:08
Контр. по Прологу Doom3 Prolog 0 22.05.2005 16:18



Powered by vBulletin® Version 3.8.7
Copyright ©2000 - 2017, Jelsoft Enterprises Ltd.
Нardforum.ru - компьютерный форум и программирование, форум программистов