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

Привет, Винитарх, это продолжение.
Цитата:
Дейкстра не ищет кратчайший путь. Он ищет древо с кроной минимального веса.
Ну хорошо. Но и кратчайший путь вполне можно найти.
Цитата:
Попробуй с помощью Дейкстры найти из заданной вершины путь минимального веса длиной n-5 на графе с n вершинами. Для начала n=100. Т.е. в предложенной мною задаче задана не конечная вершина а длина пути. У тебя этого никогда не получится...
Никто не утверждает, что этот алгоритм универсален и подходит для поиска всего, чего угодно.
Но я бы не стала сразу утверждать, что эту задачу нельзя свести к какой-нибудь другой задаче (пусть даже с потерей эффективности), к решению которой заведомо нельзя было бы применить алгоритм Дейкстры.
Цитата:
Если бы Дейкстра помечал вершины для каждой ветви собственными метками, то он бы искал дерево цепей, число которых (n-1)!. Причём одна цепь была бы Гамильтоновым путём.
Нет предела фантазиям, но может есть и другие способы?
Цитата:
Но это уже NP-полная задача и это уже алгоритм с факториальной сложностью.
Я бы сказала, с экспоненциальной, но это не важно.
Цитата:
Использование принципа оптимальности Беллмана для NP-полных задач порочно, ибо уводит вычисления в необозримую бесконечность.
???? Но, может, и разумно можно как-то использовать? А не придумать что-то и сказать, что это плохо.
Цитата:
Прошу прощения за менторский тон.
Видимо, в силу моей необразованности в этом вопросе я его не почувствовала.

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

И тут получается, например, для задачи со сдачей 88 и монетами 27, 21, 5, 3.
Если делать полным перебором с оценкой на 1 шаг вперед, то для поиска оптимального решения надо будет перебрать 97 подмножеств (все - по 3, по 4 и по 5).
А если строить граф абсолютно со всеми задачами, без каких-либо дополнительных ограничений, то вершин-задач будет более 100 (~120). Так что Дейкстру применить можно, но не нужно, если не использовать дополнительных ограничений.

P.S. Все предыдущие вопросы, в общем-то, риторические.
Учебный год начался ...
Ответить с цитированием
  (#33 (permalink)) Старый
Винитарх Винитарх вне форума
Специалист
 
Аватар для Винитарх
 
Сообщений: 7,908
Сказал(а) спасибо: 2
Поблагодарили 297 раз(а) в 297 сообщениях
Регистрация: 01.03.2003
Адрес: Краснодар
По умолчанию 04.09.2006, 20:49

Alison пишет:
Цитата:
Если нужно найти путь между двумя заданными вершинами, то все дерево целиком можно не строить.
Строить дерево НАДО!!! Без этого никак у Дейкстры не получится. А вот целиком или частично - всё зависит от удалённости искомой вершины от стартовой.

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

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

Alison пишет:
Цитата:
Эффективность да, а завершаемость всегда, если решение существует.
А если алгоритм завершиться через пару сотен (тысяч) лет, то этот алгоритм ты тоже называешь завершаемым?

Alison пишет:
Цитата:
У меня возникло подозрение, что раз в этой задаче про сдачу вполне можно применить алгоритм Дейкстры
Применить можно, но какой толк от этого применения если этот алгоритм не завершится?

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

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

Alison пишет:
Цитата:
Нет предела фантазиям
Это не фантазии. Это способ лексикографического обхода графа, заданного неупорядоченной БД вершин и рёбер.

Alison пишет:
Цитата:
Я бы сказала, с экспоненциальной, но это не важно.
Для практики это не важно, ибо и экспонента и факториал - всё это смертельный номер для Беллмана (Дейкстры и проч.). Однако теоретически рост экспоненты отличен от роста факториала. Поэтому если мы хотим быть точными в формулировках, то следует остановиться именно на ФАКТОРИАЛЬНОЙ сложности.

Alison пишет:
Цитата:
Но, может, и разумно можно как-то использовать? А не придумать что-то и сказать, что это плохо.
Вот об этом то я и говорю постоянно!!!
Необходим другой принцип оптимальности для решения NP-полных задач.

Alison пишет:
Цитата:
Мне кажется, что в некоторые твои утверждения иногда не помешало бы добавить немножко осторожности и корректности.
У нас же не научный форум, а вполне свободный, так сказать демократический и ко всем лояльный форум. Вполне допускается высказывать бредовые идеи бредовым языком не предупреждая об этом собеседников. )

Alison пишет:
Цитата:
И тут получается, например, для задачи со сдачей 88 и монетами 27, 21, 5, 3.
Если делать полным перебором с оценкой на 1 шаг вперед, то для поиска оптимального решения надо будет перебрать 97 подмножеств (все - по 3, по 4 и по 5).
А если строить граф абсолютно со всеми задачами, без каких-либо дополнительных ограничений, то вершин-задач будет более 100 (~120). Так что Дейкстру применить можно, но не нужно, если не использовать дополнительных ограничений.
А если сдача большая и монеток примерно с миллион, то Дейкстру тоже "применить можно"?
Хотя наверное можно, в смысле нажать кнопку "Пуск алгоритма Дейкстры"

Странно. Теги quote не работают
Ответить с цитированием
  (#34 (permalink)) Старый
Alison Alison вне форума
Member
 
Сообщений: 4,771
Сказал(а) спасибо: 0
Поблагодарили 119 раз(а) в 116 сообщениях
Регистрация: 17.11.2004
По умолчанию 04.09.2006, 21:43

Цитата:
Странно. Теги quote не работают
Потому что их слишком много для одного сообщения: см. туда
Поэтому я и делила свое сообщение на 2.

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

Цитата:
Строить дерево НАДО!!! Без этого никак у Дейкстры не получится. А вот целиком или частично - всё зависит от удалённости искомой вершины от стартовой.
В чем предмет спора-то? То же самое я и писала.
Цитата:
Мыслю образами, а не научными терминами, потому и реку соОбразно мыслям. Думал, что понято будет
Старая песня.
Но учти, что для серьезных дел это дешевое оправдание для некорректного манипулирования терминами.
Цитата:
"поверхность кроны" - множество терминальных вершин ветвей древа.
Что такое "терминальная" вершина? Лист, что ли, по-простому, т.е. вершина, не имеющая потомков?
Цитата:
"псевдосфера" - поверхность кроны древа, которая при больших n приближается по форме к сфере.
Множество листьев-концевых вершин, что-ли?
Цитата:
"изометрическая псевдосфера" - при больших n вес ветвей кроны слабо отклоняется от своего мат.ожидания.
Что-то новенькое - мат.ожидание ветвей. Это что такое? Как оно определяется?
Цитата:
Полагаю, что дисперсия маловата будет,
Это с какой радости? И что за случайную величину-то ты рассматриваешь?
Даже не зная, о чем речь идет, сомневаюсь, что дисперсия маловата будет. С какой стати?
Цитата:
поэтому мат.ожидание можно назвать радиусом сферы, а множество терминальных вершин ветвей кроны - равноудалёнными (с точностью до среднеквадартичного отклонения) от центра сферы, или по другому - изометрическими.
Прям песня!

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


Цитата:
Ты предлагала его использовать для поиска сдачи. Я ответил, что этого делать не стоит, так как задача про сдачу и алгоритм Дейкстры находятся в разных весовых категориях: Дейкстра в лёгком весе, оптимальная сдача - в тяжёлом.
Но ты-то сразу стал фантазировать еще о каких-то задачах, которые здесь были ни при чем.
А Дейкстру - смотря как применять.
Цитата:
Это не фантазии. Это способ лексикографического обхода графа, заданного неупорядоченной БД вершин и рёбер.
А при чем здесь он вообще??
Цитата:
Для практики это не важно, ибо и экспонента и факториал - всё это смертельный номер для Беллмана (Дейкстры и проч.). Однако теоретически рост экспоненты отличен от роста факториала. Поэтому если мы хотим быть точными в формулировках, то следует остановиться именно на ФАКТОРИАЛЬНОЙ сложности.
Забудь ты наконец о Беллмане. Что он тебе покоя не дает?
А насчет факториала и экспоненты и точности в формулировках - что такое формула Стирлинга, ты знаешь?
Мне, например, об этом читать странно.
Цитата:
Вот об этом то я и говорю постоянно!!!
Необходим другой принцип оптимальности для решения NP-полных задач.
Так о чем ты споришь? Разве кто-нибудь говорил о чем-то другом? Кроме тебя о Беллмане никто не вспоминал.

И вообще, я про Фому (точное решение), а ты про Ерему (приближенное решение).
Я повторюсь - это разные задачи.

Цитата:
А если сдача большая и монеток примерно с миллион, то Дейкстру тоже "применить можно"?
Хотя наверное можно, в смысле нажать кнопку "Пуск алгоритма Дейкстры".
А для такой задачи ты хоть с Беллманом и Дейкстрой, хоть без них, никаким из своих личных способов точное решение не найдешь.
Так чего об этом говорить во время обсуждения способов поиска ТОЧНОГО решения.
Я всякий раз оговаривалась, что говорю исключительно о том, как можно попытаться найти именно точное решение.
Ответить с цитированием
Ads.
  (#36 (permalink)) Старый
Винитарх Винитарх вне форума
Специалист
 
Аватар для Винитарх
 
Сообщений: 7,908
Сказал(а) спасибо: 2
Поблагодарили 297 раз(а) в 297 сообщениях
Регистрация: 01.03.2003
Адрес: Краснодар
По умолчанию 07.09.2006, 12:45

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

Цитата:
Это с какой радости? И что за случайную величину-то ты рассматриваешь?
Даже не зная, о чем речь идет, сомневаюсь, что дисперсия маловата будет. С какой стати?
Случайная величина - средний вес ветвей. Сомневаешься - проверь опытно.

Цитата:
о практических способах поиска точного решения я полагаю, говорить бессмысленно.
Правильно. Я ж про это и говорю, мол надо обсуждать приближённые способы, т.к. заведомо известно, что точного практического способа нет. А ПРИНЦИПИАЛЬО не реализуемые на практике способы лично меня вообще не интересуют. Зачем о них рассуждать, если это пустая трата времени?

Цитата:
Очень даже завершится. Это можно доказать. А когда завершится - не обсуждалось.
...
Да, он работает и дает точное решение. Когда - вопрос отдельный. Так что я думаю, что тебе надо уточнить слово "работает", которое ты употребляешь безо всяких уточнений.
Отмазы.
Я вообще то сугубо ПРАКТИК и создавать вечный двигатель не собираюсь. Алгоритм должен быть завершаемым.
Если алгоритм не завершается за время жизни одного поколения людей, то этот алгоритм не работает, этот алгоритм прикалывается над нами. Алгоритмы нужны для удовлетворения нужд человека, его запустившего и после его смерти они теряют смысл. Во как!

Цитата:
Глючный, это значит неправильно реализованный, а это пробема того, кто реализует.
Эээ нет. Глючный это значит имеющий глюк. Бесконечный цикл - один из видов глюка. Бесконечный потому что конца работы цикла человек его запустивший не увидит.
И проблема глючности это проблема не автора программы, а юзера.

Цитата:
И уже договорились вроде бы, что не всю крону (не все дерево).
Хе. Априорно не известно - всю крону или не всю. И даже когда не всю, то всё равно - КРОНУ.

Цитата:
формула Стирлинга
Функцию x^x ты называешь экспонентой? А как же ты называешь функцию e^x ?

Цитата:
И вообще, я про Фому (точное решение), а ты про Ерему (приближенное решение).
Я повторюсь - это разные задачи.
Задача одна и та же. Просто математики ищут точное решение, хотя точно знают, что его никогда не найдут. Ищут просто так, из-за любви к поиску.
Практики ищут приближённое решение потому что точно знают, что его найдут. Ищут не просто так, а за еду.

Цитата:
Я всякий раз оговаривалась, что говорю исключительно о том, как можно попытаться найти именно точное решение.
Тогда пардон. А я говорил о хоть каком-нибудь стОящем решении для задачи с произвольной размерностью данных.
Ответить с цитированием
Ads
  (#37 (permalink)) Старый
Alison Alison вне форума
Member
 
Сообщений: 4,771
Сказал(а) спасибо: 0
Поблагодарили 119 раз(а) в 116 сообщениях
Регистрация: 17.11.2004
По умолчанию 07.09.2006, 22:01

Цитата:
Погоняй задачу на графах, набери статистику в несколько сотен тысяч опытов, посчитай среднее арифметическое веса ветвей и дисперсию.
Не буду. То есть речь о статистических данных для конкретного набора графов с неизвестно для меня какими характеристиками (видимо, с вполне определенными).
Цитата:
Случайная величина - средний вес ветвей. Сомневаешься - проверь опытно.
Тут все зависит от того, какие именно графы ты рассматриваешь. У тебя же они не произвольные.
Возьмем, например, последовательность графов, состоящих из одного ребра.
В первом графе вес ребра равен 1, во втором 2, в третьем 3 и т.д.
Что ты тут скажешь о среднем весе и, особенно, о среднем квадратическом отклонении (оно заведомо велико, если число графов, например, сто тысяч)?
Цитата:
Я ж про это и говорю, мол надо обсуждать приближённые способы, т.к. заведомо известно, что точного практического способа нет.
Есть, для небольших данных. И здесь некоторые способы есть.
Цитата:
Априорно не известно - всю крону или не всю. И даже когда не всю, то всё равно - КРОНУ.
Ты так и не пояснил, что это такое. И что такое терминальная вершина.
Цитата:
Функцию x^x ты называешь экспонентой? А как же ты называешь функцию e^x ?
x^x=e^(xlnx).
Цитата:
А я говорил о хоть каком-нибудь стОящем решении для задачи с произвольной размерностью данных.
О решении - не говорил.
Ответить с цитированием
  (#38 (permalink)) Старый
Винитарх Винитарх вне форума
Специалист
 
Аватар для Винитарх
 
Сообщений: 7,908
Сказал(а) спасибо: 2
Поблагодарили 297 раз(а) в 297 сообщениях
Регистрация: 01.03.2003
Адрес: Краснодар
По умолчанию 08.09.2006, 12:59

Цитата:
Тут все зависит от того, какие именно графы ты рассматриваешь.
Полные графы, т.к. после прибавления одной монеты я могу взять следующую произвольного номинала (и больше предыдущей, и меньше). n - большое (я это уже упоминал). Вес рёбер случайный с произвольным законом распределения на всех (n^2 - n)/2 рёбрах. Это потому, что мы можем взять в качестве очередной - ЛЮБУЮ монету.

Цитата:
Есть, для небольших данных.
Для небольших (я бы сказал маленьких) - есть. Но для практики число данных должно быть хотя бы пару сотен. Потянет твой способ на двух сотнях монетках?

Цитата:
Ты так и не пояснил, что это такое. И что такое терминальная вершина.
Крона - это ВСЕ ПУТИ (цепи) дерева до листа включительно.
Терминальная вершина пути - последняя вершина пути.

Цитата:
x^x=e^(xlnx).
Опять ты за своё!
Рост функций x! и e^x совершенно разный. Поэтому говоря "факориальный рост от x" я выразил мысль точно, т.к. читатель под этим понимает x!. Если бы я сказал "экспоненциальный рост от x", то читатель наверняка бы подумал e^x, что гораздо медленней, нежели x!, и эта неточность есть обман особенно при больших x.

Цитата:
О решении - не говорил.
Нет, О решении я как раз упоминал в самом начале. А вот само решение я не описывал.
Ответить с цитированием
  (#39 (permalink)) Старый
Alison Alison вне форума
Member
 
Сообщений: 4,771
Сказал(а) спасибо: 0
Поблагодарили 119 раз(а) в 116 сообщениях
Регистрация: 17.11.2004
По умолчанию 08.09.2006, 13:59

Цитата:
Полные графы, т.к. после прибавления одной монеты я могу взять следующую произвольного номинала (и больше предыдущей, и меньше). n - большое (я это уже упоминал). Вес рёбер случайный с произвольным законом распределения на всех (n^2 - n)/2 рёбрах. Это потому, что мы можем взять в качестве очередной - ЛЮБУЮ монету.
А вот об этом, пожалуйста, поподробнее, если хочешь, чтобы тебя понимали.
Каким именно образом ты моделируешь эту задачу в виде полного графа?
Что из себя представляют вершины, а что ребра?
И вообще, почетче и поконкретнее.
Цитата:
Но для практики число данных должно быть хотя бы пару сотен. Потянет твой способ на двух сотнях монетках?
Это же фактически полный перебор для количества подмножеств, которое я указывала выше (реально - немного меньше). Видимо, все зависит от величины сдачи. Но точный способ в данном случае и не должен годиться для больших данных. Это очевидно.
Тем более, что и у тебя способа найти точное решение для таких данных не существует.
Цитата:
Рост функций x! и e^x совершенно разный.
Кто бы сомневался! Только о них и речи не было, совсем!
Цитата:
Поэтому говоря "факориальный рост от x"
Почитай еще раз свои предыдущие посты! Ни разу и нигде не было не было такого выражения, и речи о нем не было.
Кого ты хочешь ввести в заблуждение, и зачем?
Цитата:
я выразил мысль точно,
В данном случае нет, я только все надеюсь увидеть точное выражение мысли.
Цитата:
Если бы я сказал "экспоненциальный рост от x"
Естественно, "экспоненциальный рост от x" - это O(a^x), где a>1.
Но про рост от х не было ни слова!
Я привела точное количество подмножеств для перебора, а ты о точных вещах и каких-либо оценках ничего определенного вообще не говорил (например, откуда ты взял "факториальную" сложность в этой задаче и почему это слово тебе больше нравится, чем слово "экспоненциальная").
Цитата:
то читатель наверняка бы подумал e^x, что гораздо медленней, нежели x!, и эта неточность есть обман особенно при больших x.
Смешно. Ты же практик?
Ну, давай про экспоненциальный рост на практике.
Возьми листок бумаги. Разрежь его пополам, сложи половинки друг на друга, опять разрежь пополам, и т.д. Выполни эту операцию 100 раз. А теперь оцени высоту стопки бумаги, которая получится, если считать, что пачка бумаги 500 листов имеет высоту 5 см.
Получится представление об экспоненциальном росте не только по зависанию компьютера при уходе в далекий цикл.
Итого: для больших данных эта "неточность" на практике не имеет ровным счетом никакого значения. О каком обмане практиков может идти речь?
Если алгоритм уже имеет экспоненциальную сложность, то о чем говорить дальше (тем более, что у более сложного алгоритма нужно еще правильно оценить сложность)?
И о каком читателе может идти речь?
Цитата:
Нет, О решении я как раз упоминал в самом начале. А вот само решение я не описывал.
То есть только то, что решение в принципе существует (как часто бывает в математике, и чем ты недоволен обычно). А обсуждать-то и нечего.
Ответить с цитированием
  (#40 (permalink)) Старый
Alison Alison вне форума
Member
 
Сообщений: 4,771
Сказал(а) спасибо: 0
Поблагодарили 119 раз(а) в 116 сообщениях
Регистрация: 17.11.2004
По умолчанию 08.09.2006, 15:23

Еще раз о сложности для задачи про сдачу.

Пусть n - число различных монет в исходном наборе,
k = Сдача div наиб_монета,
M = Сдача div наим_монета.

Тогда, если делать вообще полный перебор, то самое большее нужно перебрать вот столько "подмножеств" (точнее, наборов монет - элементы могут повторяться):

C(n+k-1,k) + C(n+k,k+1) + C(n+k+1,k+2)+...+C(n+M-1,M).

т.е. все сочетания с повторениями из n по k, по k+1, ..., по M (больше просто не может быть).
Это число равно (по свойствам чисел сочетаний):

C(n+k-1,n-1) + C(n+k,n-1) + C(n+k+1,n-1)+...+C(n+M-1,n-1)=
=(C(n+k,n)-C(n+k-1,n))+(C(n+k+1,n)-C(n+k,n))+...+(C(n+M,n)-C(n+M-1,n))=
=C(n+M,n)-C(n+k-1,n)

Это точное количество абсолютно всех "подмножеств" (вообще говоря, с повторяющимися элементами).
Теперь простая оценка:

C(n+M,n)-C(n+k-1,n) < C(n+M,n) <= C(n+M,[n+M/2]) ~ const*(2^(n+M)) / sqrt(n+M).

Последнее выражение получено по формуле Стирлинга.

Т.е. при полном переборе нужно перебрать менее, чем Сonst*(2^(n+M)) / sqrt(n+M) подмножеств (с повт. элементами).
А это не больше "экспоненты".

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

Цитата:
Полные графы, т.к. после прибавления одной монеты я могу взять следующую произвольного номинала (и больше предыдущей, и меньше). n - большое (я это уже упоминал). Вес рёбер случайный с произвольным законом распределения на всех (n^2 - n)/2 рёбрах. Это потому, что мы можем взять в качестве очередной - ЛЮБУЮ монету.
Пытаюсь понять (никакой литературы по данному вопросу я никогда не видела, видимо, потому что и не искала).
1. "мы можем взять в качестве очередной - ЛЮБУЮ монету".
Наверное, раз и равную предыдущей тоже, то всего возможностей n.

2. "Вес рёбер случайный".
Хорошо.
Для начала можно рассмотреть простейший случай, когда на очередном шаге каждая монета может быть взята с равной вероятностью (а как у тебя?).
Тогда приближ. решение можно представить как X=(X1, X2, ..., Xm), где Xi - случайная величина - вес монеты, взятой на i-м шаге.
Т.е. прибл. решение - это набор m одинаково распределенных случайных величин (со всеми вытекающими из этого последствиями), сумма значений которых в каждом наборе близка к Сдаче.
Среднее суммы, видимо, равно Сдаче, а m - это случайная величина, которая может принимать значения от k до M.

Получается, что всегда в запасе есть два грубых, простейших метода для поиска приближенного решения (вообще говоря, далекого от оптимального).
1. Метод "по Беллману". Брать всегда наибольшую из доступных монет.
2. Метод "тыка". Взять некоторое количество случайных решений и выбрать то, где m минимально.

Оба метода (в модифицированном виде), в принципе, можно использовать для каких-либо предварительных прикидок. Т.е. сначала прикидки, потом уточнения.

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

Думаю, что случайный выбор ни при чем, и не надо брать любую монету.
А перебор вместе с Беллманом может привести к неплохим результатам.

Например, для сдачи 88 и набора монет {27, 21, 5, 3}.
(27, 27, 27, 5) (недостаток 2)
(27, 27, 27, 5, 3) (избыток 1)
(27, 27, 27, 3, 3) (недостаток 1)
(27, 27, 21, 21) (избыток 8 )
(27, 27, 21, 5, 5, 3) (точно) - повезло. Число монет 6.
Теперь можно посмотреть, что будет для 4 и 5 монет (оставшиеся варианты).
(27, 21, 21, 21) (избыток 3)
(21, 21, 21, 21, 5) (избыток 1)
(21, 21, 21, 21, 3) (недостаток 2)
Остальные отсеиваются, т.к. в остаток помещаются еще монеты целиком, поэтому они не могут быть прибл. решениями.
Ответить с цитированием
  (#43 (permalink)) Старый
Винитарх Винитарх вне форума
Специалист
 
Аватар для Винитарх
 
Сообщений: 7,908
Сказал(а) спасибо: 2
Поблагодарили 297 раз(а) в 297 сообщениях
Регистрация: 01.03.2003
Адрес: Краснодар
По умолчанию 11.09.2006, 22:33

В качестве полного перебора я имел в виду не сочетания, а перестановки. Уж полный, так полный.
Ответить с цитированием
  (#44 (permalink)) Старый
Alison Alison вне форума
Member
 
Сообщений: 4,771
Сказал(а) спасибо: 0
Поблагодарили 119 раз(а) в 116 сообщениях
Регистрация: 17.11.2004
По умолчанию 11.09.2006, 22:43

Но наборы, отличающиеся лишь перестановкой элементов, одинаковы.

Зачем искусственно усложнять поиск и сложность задачи?
Это более, чем странно (и неправильно).
Ответить с цитированием
  (#45 (permalink)) Старый
Винитарх Винитарх вне форума
Специалист
 
Аватар для Винитарх
 
Сообщений: 7,908
Сказал(а) спасибо: 2
Поблагодарили 297 раз(а) в 297 сообщениях
Регистрация: 01.03.2003
Адрес: Краснодар
По умолчанию 12.09.2006, 17:46

Alison пишет:
Цитата:
каждая монета может быть взята с равной вероятностью (а как у тебя?).
Я вижу так:
Вероятность "взятия" монеты пропорциональна её "близости" к сдаче. При этом Беллмановские локальные решения будут иметь наибольшую вероятность и это понятно. Однако Беллмановское глобальное решение только одно и хотя оно имеет наибольшие шансы быть "победителем", всё-таки эти шансы ничтожно малы и при больших n шансы стремятся к нулю.
И вот здесь возникает интересный вопрос: а какие ещё околобеллмановские варианты можно просмотреть, у которых шансы тоже некислые? И вообще, хотелось бы ВСЕ варианты решений УПОРЯДОЧИТЬ по убыванию этих самых шансов и проверять эти решения от самых вероятных до самых невероятных.
Короче, этот вопрос решён теоретически и практически с помощью ранжированного дерева поиска решения (ты его видела на конференции), и прекрасно работает при поиске min/max путей на графах, заданных только длиной (или длиной и стартовой вершиной), а также min/max циклов на графах, а также на всех задачах, подобных этим с т.з. УПОРЯДОЧЕНИЯ просмотра вариантов, т.е. мои любимые раскладухи - ортогональные (гильотинные и негильотинные) и криволинейные (нестинг) и прочие NP-задачи в оптимальной постановке, т.е. там, где допускается приближённые решения.
Остановка алгоримта возможна либо по достижению априорно заданной границы решения (целевой функции), либо по времени, либо по количеству просмотренных вариантов. Т.е. налицо большая гибкость. Реализован и хорошо работает именно последний вариант - просмотр априорно заданного количества вариантов.
Ты же всё видела на конференции:
Каждый вариант решения представляется рангами своих локальных решений. Один из самых простых способов - перебор решений, сумма рангов локальных решений которых не превосходит априорно заданного числа S. На практике хватает S=3 для не очень большого n. При большом n можно взять S=2.
Ответить с цитированием
Ответ

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

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

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 - компьютерный форум и программирование, форум программистов