Главная страница « Информация « 4 курс « курс ВвФП «

Варианты задания «Генетическое программирование». 2015-16 учебный год

„Нет проблем! Мы можем покончить с этой ерундой за выходные!“
Э. Йордон „Путь камикадзе“

Задание разработано к. ф.-м. н. А. В. Черновым и использовалось при ведении практикума 327, 328 групп в течение ряда лет. Из-за того, что сейчас не используется система автоматического тестирования, в исходный текст были внесены изменения. Также добавлены несколько не использованных в прошлом вариантов задач.

Решите предлагаемые задачи, используя алгоритмы «генетического программирования». Вам необходимо самостоятельно определить, что является «хромосомой», «популяцией», как выполняется «скрещивание», «мутация» и «отбор лучших особей». В процессе реализации метода необходимо подобрать параметры «генетического алгоритма» таким образом, чтобы добиться наилучшей скорости сходимости и точности.

Все задачи сформулированы в виде задач проверки свойств, то есть требующих ответ #f или #t в зависимости от того, существует ли какое-либо решение задачи, удовлетворяющее указанным свойствам. Однако в случае если решение существует, должно быть напечатано решение, оптимальное по некоторому параметру.

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

Следует использовать версию языка scheme/base (начинайте свой код с директивы #lang scheme/base). Использование в программе мутаторов (присваиваний и т. п.) запрещено. Разрешено использовать библиотеки из Racket Core Libraries и только их.

Выполнения задания разделено на четыре этапа. На первом этапе разрабатываются тесты, на которых будет проверяться программа. Набор тестов должен быть достаточно большим. В набор должны входить тесты, на каждый вариант ответа (на #f и на #t). Для каждого теста должен быть известен ответ. В набор должны входить тесты достаточно большого объема. Предполагается, что из-за большого объема тесты будут генерироваться с помощью составленной Вами вспомогательной программы. Программа, генерирующая тесты, сдается вместе с тестами. Также сдается программа (или скрипт/скрипты не на Scheme), автоматизирующие процесс тестирования. Будьте готовы дать пояснения и обоснования выбранных Вами тестовых случаев, способов генерации тестов, организации тестирования. Максимальная оценка за 1-й этап -- 5 баллов. Срок сдачи без штрафа: по 20 октября включительно.

На втором этапе разрабатывается версия программы, которая находит решение, но не выполняет визуализацию. Программа должна проходить все тесты с первого этапа и, возможно, дополнительные тесты. Код программы должен быть правильно оформлен, структурирован, сопровожден комментариями. Максимальная оценка за 2-й этап -- 15 баллов. Срок сдачи без штрафа: по 17 ноября включительно.

На третьем этапе сдается полная версия программы, выполняющая и решение задачи, визуализацию хода решения, визуализацию найденного ответа. На этом этапе можно использовать Racket Drawing Toolkit, Racket Graphical Interface Toolkit, пакет plot. Качество визуализации влияет на оценку за этап. Максимальная оценка за 3-й этап -- 15 баллов. Срок сдачи без штрафа: по 1 декабря включительно. Баллы за этап делятся на две части: до 10 баллов за обязательную часть и до 5 баллов за творческую часть. Обязательная часть включает в себя визуализацию найденного решения и визуализацию (с помощью одного изображения) процесса приближения текущего решения задачи к оптимальному (итоговому). Этот процесс можно визуализировать графиками, отражающими характеристики популяций на всех итерациях. Можно выводить показатели лучшей особи в популяции, худшей особи и средний показатель. Визуализацию не обязательно выполнять по ходу решения. Если решение задачи идет медленно, то предпочтительнее схема, при которой сбор данных о ходе решения и построение картинки разделены. Творческая часть состоит в реализации «потребительских» качеств визуализации. Есть ли интерактив? Статическая ли картинка или анимированная? Удачно ли цветовое и композиционное решение? Какие дополнительные сведения помимо обязательных визуализируются?

На завершающем 4-м этапе готовится отчет о выполненном задании. Отчет сдается по электронной почте в электронной форме в формате PDF. Требования к отчету указаны ниже. Максимальная оценка за 4-й этап -- 5 баллов. Срок сдачи без штрафа: по 19 декабря включительно.

На всех этапах за каждую неделю просрочки сдачи этапа будет начисляться штраф в размере 1/4 от максимального балла. По прошествии 4-х недель этап можно сдать, но баллы начислены не будут. Студенты не сдавшие задание не смогут получить положительную оценку на экзамене.

Требования к отчету

Отчет пишется на русском языке. Текст отчета должен быть разбит на следующие части:

• Титульный лист, с «шапкой» - «Московский государственный университет имени М. В. Ломоносова, факультет Вычислительной математики и кибернетики». Далее следует заголовок: «Отчет по второму заданию», номер и тема варианта задания, сведения об исполнителе (фамилия, имя и отчество полностью, номер группы). Внизу титульного листа указывается город и год. Нелишне обратить внимание на то, что точки после заголовков не ставятся.
  

• Содержание состоит из перечня названий глав и подглав, сопровождаемых указанием номеров страниц, с которых они начинаются. Нумеруются все страницы, за исключением титульного листа. Номер страницы с содержанием: 2.
  

• Первая глава, названная «Постановка задачи», содержит формулировку задания. Каждую главу следует начинать с новой страницы.
  

• Вторая глава, названная «Генерация тестов», содержит описание рассматриваемых тестовых случаев, описание параметров тестовых наборов, основные детали реализации генератора тестов, пояснения по организации автоматизированного тестирования.
  

• Третья глава, названная «Генетический алгоритм», содержит описание хромосомы, описание способа создания начальной популяции, описание оценочной функции, описание операций скрещивания и мутации, описание способа отбора, описание критерия останова, изменения в традиционной схеме генетического алгоритма (если таковые были сделаны), основные детали реализации генетического алгоритма.
  

• Четвертая глава, названная «Визуализация», содержит описание визуализации найденного решения и процесса приближения текущего решения задачи к оптимальному. Следует указать реализованные возможности по «творческой части» (показ дополнительных сведений, анимация, интерактив и т. п.) и привести основные сведения по реализации.
  

• Пятая глава, названная «Результаты», содержит анализ результатов работы программы. Следует охарактеризовать результаты, полученные на тестовых наборах, которые относятся к разным тестовым случаям. Если на каких-то тестовых наборах получены неоптимальные или неверные результаты, следует проанализировать причины этого. Необходимо привести сведения о времени, которое ушло на выполнение тестов.
  

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

• Список использованной литературы приводится, если в ходе работы над заданием были использованы статьи и/или книги. Библиографические записи в списке следует оформлять по рекомендациям ГОСТ. На каждую запись списка в тексте отчета должна быть ссылка.
  

• Приложение, которое содержит Ваш код.

На всякий случай, приведен вид страницы с содержанием (без указания номеров страниц для 2 главы и последующих частей отчета)
Содержание
1. Постановка задачи ....................3
2. Генерация тестов ......................
3. Генетический алгоритм .................
4. Визуализация ..........................
5. Результаты ............................
Заключение ...............................
Список литературы ........................
Приложение. Код программы.................

1. Упаковка в контейнеры

2. Задача о рюкзаке

3. Раскраска вершин графа

4. Раскраска ребер графа

5. Доминирующее множество вершин

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

7. Расписание заданий в многопроцессорной системе

8. Клика

9. Прямоугольное сжатие картинки

10. Разрезание циклов вершинами

11. Задача о ранце

12. Разрезание циклов ребрами

13. Независимое множество

14. Максимальный разрез графа

15. Доминирующее множество ребер

16. Выполнимость КНФ

17. Задача сельского почтальона

18. Задача о рюкзаках

На вход программе подаются два списка: список длины N (N > 0) весов предметов W_i (W_i >0, 1≤i≤N) и список длины K (K >0) вместимостей контейнеров C_j (C_j >0, 1≤ j ≤K). Все веса и вместимости -- целые числа.
Существует ли такое разбиение N предметов по K контейнерам, что для каждого предмета i есть контейнер j, в котором он размещен, и для каждого контейнера j вес всех предметов, в нем размещенных, не превышает C_j? Если такое разбиение существует, напечатайте #t, затем количество использованных контейнеров, а затем само разбиение. Если разбиения не существует, напечатайте #f.
Из всех допустимых разбиений выберете разбиение, которое использует минимальное количество контейнеров. Разбиение печатайте в виде списка содержимого контейнеров. Содержимое контейнера -- это список номеров размещенных в нем предметов.
В процессе нахождения решения должна быть предусмотрена визуализация процесса приближения текущего решения задачи к оптимальному. Предусмотрите возможность визуализации результата.
Пример входных данных:
(1 2 2 3)
(4 4)
Пример печати результата:
#t
2
((1 4) (2 3))

На вход программе подаются два списка длины N (N > 0) список весов предметов W_i (W_i > 0, 1 ≤ i ≤ N) и список их стоимостей C_i (C_i > 0, 1 ≤ i ≤ N). Все веса и стоимости предметов -- целые числа. Затем на вход программе подаются два целых числа B (B > 0) и K (K > 0).
Существует ли такое подмножество предметов, для которого суммарный вес предметов в этом подмножестве не превышает B, а суммарная стоимость предметов не меньше K? Если такого подмножества не существует, напечатайте #f. Если такое подмножество существует, напечатайте #t, затем суммарный вес предметов, их суммарную стоимость, а затем список номеров предметов, вошедших в это подмножество. Из всех возможных разбиений выберите такое, которое максимизирует суммарную стоимость предметов в рюкзаке.
В процессе нахождения решения должна быть предусмотрена визуализация процесса приближения текущего решения задачи к оптимальному. Предусмотрите возможность визуализации результата.
Пример входных данных:
(1 1 2 2)
(4 3 2 1)
3
4
Пример печати результата:
#t
2
7
(1 2)

На вход программы подается список ребер неориентированного графа G = (V, E). Вершины v_i∈V обозначаются атомами, ребра представляются списками вида (NODE1 NODE2). Затем на вход программы подается целое число K (1 ≥ K).
Можно ли раскрасить вершины графа G не более чем в K цветов, то есть существует ли функция c : V → {1. . .K} такая, что если (u, v)∈E, то c(u) ≠ c(v)? Если раскраски вершин графа в K цветов не существует, напечатайте #f. Если раскраска вершин графа существует, то сначала напечатайте #t, затем количество цветов, в которые раскрашен граф, а затем список вершин с указанием их цветов. Элементами этого списка являются списки из двух элементов следующего вида (NODE COLOR). Из всех возможных вариантов раскраски выберите тот, который требует минимального количества цветов.
В процессе нахождения решения должна быть предусмотрена визуализация процесса приближения текущего решения задачи к оптимальному. Предусмотрите возможность визуализации результата.
Пример входных данных:
((a b) (b c) (c d) (a d))
2
Пример печати результата:
#t
2
((a 1)(b 2)(c 1)(d 2))

На вход программы подается список ребер неориентированного графа G = (V, E). Вершины v_i∈V обозначаются атомами, ребра представляются списками вида (NODE1 NODE2). Затем на вход программы подается целое число K (1 ≤ K).
Можно ли раскрасить ребра графа G не более чем в K цветов, то есть существует ли функция c : E → {1. . .K} такая, что если (u, v), (u, w), (x, u) ∈E, то c((u, v)) ≠ c((u, w)) и c((u, v)) ≠ c((x, u)) при v ≠ w и v ≠ x? Если раскраски ребер графа в K цветов не существует, напечатайте #f. Если раскраска ребер графа существует, то сначала напечатайте #t, затем количество цветов, в которые раскрашен граф, а затем список ребер с указанием их цветов. Элементами этого списка являются списки из двух элементов следующего вида ((NODE1 NODE2) COLOR). Из всех возможных вариантов раскраски выберите тот, который требует минимального количества цветов.
В процессе нахождения решения должна быть предусмотрена визуализация процесса приближения текущего решения задачи к оптимальному. Предусмотрите возможность визуализации результата.
Пример входных данных:
((a b) (b c) (c d) (a d))
2
Пример печати результата:
#t
2
((a b) 1)((b c) 2)((c d) 1)((a d) 2))

На вход программы подается список ребер неориентированного графа G = (V, E). Вершины v_i∈V обозначаются атомами, ребра представляются списками вида (NODE1 NODE2). Затем на вход программы подается целое число K (1 ≤ K).
Существует ли в графе G доминирующее подмножество вершин, то есть такое подмножество вершин W ⊆ V, что |W| ≤ K и каждая вершина v не из этого подмножества вершин (v ∈ V-W) соединена ребром по крайней мере с одной вершиной из множества W? Если доминирующего подмножества вершин не существует, напечатайте #f. Если доминирующее подмножество вершин существует, напечатайте #t, затем количество вершин в доминирующем подмножестве, а затем список вершин, входящих в доминирующее подмножество. Из всех возможных вариантов доминирующего подмножества выберите вариант с минимальным количеством вершин.
В процессе нахождения решения должна быть предусмотрена визуализация процесса приближения текущего решения задачи к оптимальному. Предусмотрите возможность визуализации результата. Пример входных данных:
((a b) (a c) (a d))
1
Пример печати результата:
#t
1
(a)

На вход программе подается описание взвешенного неориентированного графа G = (V, E) в виде списка описаний ребер. Каждое описание ребра e ∈ E имеет вид (NODE1 NODE2 WEIGHT), где NODE1, NODE2 -- атомы, WEIGHT -- целое положительное число. Затем на вход программе подается целое положительное число K.
Существует ли в графе G гамильтонов цикл, то есть путь, начинающийся и заканчивающийся в одной и той же вершине и проходящий через каждую вершину только один раз, стоимости не более чем K? Стоимость пути -- это суммарная стоимость ребер, составляющих путь. Если гамильтонов цикл не существует, напечатайте #f. Если гамильтонов цикл существует, напечатайте #t, далее стоимость цикла, а затем гамильтонов цикл в виде списка. Первым и последним элементом списка должен быть один и тот же атом. Если существует несколько возможных гамильтоновых путей, найдите путь с минимальной стоимостью.
В процессе нахождения решения должна быть предусмотрена визуализация процесса приближения текущего решения задачи к оптимальному. Предусмотрите возможность визуализации результата.
Пример входных данных:
((a b 1) (b c 1) (c d 1) (a d 1))
4
Пример печати результата:
#t
4
(a b c d a)

На вход программе подается список длины N (N > 0) длительностей заданий T_i (T_i >0, 1≤i≤N) и K (K >0) -- количество процессоров в многопроцессорной системе и T -- контрольное время. T_i и T -- целые числа.
Существует ли такое расписание N заданий по K процессорам, что для каждого задания i есть процессор j, на котором оно выполняется, и для каждого процессора j суммарная длительность выполняемых на нем заданий не превышает контрольного времени T? Считается, что задания на каждом процессоре выполняются строго последовательно. Если такое расписание существует, напечатайте #t, затем время, необходимое для выполнения всех заданий, а затем список последовательностей номеров заданий для каждого процессора. Если расписания не существует, напечатайте #f.
Из всех допустимых расписаний выберете то, при котором минимизируется время, необходимое для выполнения всех заданий. Расписание печатайте в виде списка последовательностей номеров заданий для каждого процессора.
В процессе нахождения решения должна быть предусмотрена визуализация процесса приближения текущего решения задачи к оптимальному. Предусмотрите возможность визуализации результата.
Пример входных данных:
(1 2 2 3)
2
4
Пример печати результата:
#t
4
((1 4) (2 3))

На вход программе подается описание неориентированного невзвешенного графа G = (V, E) в виде списка описаний ребер. Вершины v_i∈V обозначаются атомами, ребра представляются списками вида (NODE1 NODE2). Затем на вход программе подается целое число K (1 ≤ K ≤ |V|).
Существует ли в графе G клика мощности, не меньшей K? Кликой графа называется полный подграф графа. Мощность клики -- это количество вершин в ней. Если такой клики не существует, напечатайте #f. Если клика существует, напечатайте #t, затем мощность клики, затем список вершин, входящих в клику. Из всех возможных решений задачи, удовлетворяющих условию, выберите решение с максимальной мощностью клики.
В процессе нахождения решения должна быть предусмотрена визуализация процесса приближения текущего решения задачи к оптимальному. Предусмотрите возможность визуализации результата.
Пример входных данных:
((a b) (b c) (c d) (a d) (a c))
3
Пример печати результата:
#t
3
(a b c)

На вход программы подается квадратная битовая матрица M размера NxN (M_ij∈{0, 1}). Матрица вводится в виде списка из N строк матрицы, где каждая строка -- это список из N элементов матрицы. Затем задается положительное целое число K.
Можно ли покрыть все единичные элементы матрицы M не более чем K прямоугольниками? Другими словами, существует ли такая последовательность четверок (a_i, b_i, c_i, d_i) (1 ≤ i ≤ K, 1 ≤ a_i, b_i, c_i, d_i ≤ N, a_i ≤ c_i, b_i ≤ d_i), в которой a_i, c_i -- это номера строк матрицы, а b_i, d_i -- номера столбцов. Эта последовательность должна удовлетворять условию, что любой единичный элемент матрицы должен покрываться хотя бы одним прямоугольником, и любой прямоугольник должен состоять только из единиц. Если такого покрытия не существует, напечатайте #f. Если покрытие существует, напечатайте #t, затем количество прямоугольников, а затем список описаний прямоугольников. Каждое описание прямоугольника представляет собой список из 4 элементов как описано выше.

В процессе нахождения решения должна быть предусмотрена визуализация процесса приближения текущего решения задачи к оптимальному. Предусмотрите возможность визуализации результата.
Пример входных данных:
((1 1 0 0) (1 1 0 0) (0 0 1 1) (0 0 1 1))
2
Пример печати результата: #t
2
((1 1 2 2) (3 3 4 4))

На вход программе подается описание невзвешенного ориентированного графа G = (V, E) в виде списка ребер. Вершины графа v_i∈V представлены атомами, а описание каждого ребра имеет вид (FROM TO). Затем на вход программе подается число K.
Существует ли в графе G такое подмножество вершин W (W ⊆ V) мощности не большей K, что каждый цикл в графе G содержит хотя бы одну вершину из множества W? Если такого подмножества вершин не существует, напечатайте #f, а если такое подмножество вершин существует, напечатайте #t, затем количество вершин в нем, а затем список вершин, входящих в это подмножество. Из всех допустимых подмножеств выберите подмножество минимальной мощности.
В процессе нахождения решения должна быть предусмотрена визуализация процесса приближения текущего решения задачи к оптимальному. Предусмотрите возможность визуализации результата.
Пример входных данных:
((a b)(b c)(c d)(d a))
1
Пример печати результата:
#t
1
(a)

На вход программе подаются три списка длины N (N > 0) список весов предметов W_i (W_i > 0, 1 ≤ i ≤ N), список объемов предметов V_i (V_i > 0, 1 ≤ i ≤ N) и список их стоимостей C_i (C_i > 0, 1 ≤ i ≤ N). Все веса, объемы и стоимости предметов -- целые числа. Затем на вход программе подаются три целых числа: предельный вес W (W > 0), предельный объем V (W > 0) и минимальную стоимость K (K > 0).
Существует ли такое подмножество предметов, для которого суммарный вес предметов в этом подмножестве не превышает W, суммарный объем предметов не превышает V, а суммарная стоимость предметов не меньше K? Если такого подмножества не существует, напечатайте #f. Если такое подмножество существует, напечатайте #t, затем суммарный вес предметов, их суммарный объем, их суммарную стоимость, а затем список номеров предметов, вошедших в это подмножество. Из всех возможных разбиений выберите такое, которое максимизирует суммарную стоимость предметов в ранце.
В процессе нахождения решения должна быть предусмотрена визуализация процесса приближения текущего решения задачи к оптимальному. Предусмотрите возможность визуализации результата.
Пример входных данных:
(1 1 2 2)
(2 1 1 2)
(1 2 3 4)
3
3
4
Пример печати результата:
#t
3
3
6
(2 4)

На вход программе подается описание невзвешенного ориентированного графа G = (V, E) в виде списка ребер. Вершины графа v_i∈V представлены атомами, а описание каждого ребра имеет вид (FROM TO). Затем на вход программе подается число K.
Существует ли в графе G такое подмножество ребер F (F ⊆ E) мощности не большей K, что каждый цикл в графе G содержит хотя бы одно ребро из множества F? Если такого подмножества ребер не существует, напечатайте #f, а если такое подмножество ребер существует, напечатайте #t, затем количество ребер в нем, а затем список ребер, входящих в это подмножество. Из всех допустимых подмножеств выберите подмножество минимальной мощности.
В процессе нахождения решения должна быть предусмотрена визуализация процесса приближения текущего решения задачи к оптимальному. Предусмотрите возможность визуализации результата.
Пример входных данных:
((a b)(b c)(c d)(d a))
1
Пример печати результата:
#t
1
((a b))

На вход программе подается описание неориентированного невзвешенного графа G = (V, E) в виде списка описаний ребер. Вершины v_i∈V обозначаются атомами, ребра представляются списками вида (NODE1 NODE2). Затем на вход программе подается целое число K (1 ≤ K ≤ |V|).
Существует ли в графе G независимое множество мощности, не меньшей K? Независимым множеством графа G называется подмножество V, в котором никакие две вершины не соединены ребром. Мощность множества -- это количество вершин в нем. Если такого множества не существует, напечатайте #f. Иначе напечатайте #t, затем мощность независимого множества, затем список вершин, входящих в него. Из всех возможных решений задачи, удовлетворяющих условию, выберите множество с максимальной мощностью.
В процессе нахождения решения должна быть предусмотрена визуализация процесса приближения текущего решения задачи к оптимальному. Предусмотрите возможность визуализации результата.
Пример входных данных:
((a b) (b c) (c d) (a d))
2
Пример печати результата:
#t
2
(b d)

На вход программе подается описание неориентированного взвешенного графа G = (V, E) в виде списка описаний ребер. Вершины v_i∈V обозначаются атомами, ребра представляются списками вида (NODE1 NODE2 WEIGHT). Затем на вход программе подается целое число K (1 ≤ K ≤ |V|).
Существует ли в графе разрез C величины, не меньшей K? Разрезом C = (S, T) графа G называется разбиение множества V вершин графа на два непустых непересекающихся подмножества S и T, таких что: S ∪ T = V, S ∩ T = ∅, |S| > 0, |T| > 0. С разрезом C = (S, T) связывают множество всех ребер исходного графа, таких что один из концов ребра является вершиной из S, другой -- вершиной из T. Величина разреза C -- это суммарный вес ребер в его множестве. Если такого разреза не существует, напечатайте #f. Иначе напечатайте #t, затем величину разреза, затем список ребер, входящих в разрез. Из всех возможных решений задачи, удовлетворяющих условию, выберите разрез максимальной величины.
В процессе нахождения решения должна быть предусмотрена визуализация процесса приближения текущего решения задачи к оптимальному. Предусмотрите возможность визуализации результата.
Пример входных данных:
((a b 2) (b c 1) (c d 1) (a d 1) (a e 1) (d e 1))
2
Пример печати результата:
#t
6
((a b 2) (b c 1) (c d 1) (a d 1) (a e 1))

На вход программы подается список ребер неориентированного графа G = (V, E). Вершины v_i∈V обозначаются атомами, ребра представляются списками вида (NODE1 NODE2). Затем на вход программы подается целое число K (1 ≤ K).
Существует ли в графе G доминирующее подмножество ребер, то есть такое подмножество ребер F ⊆ E, что |F| ≤ K и каждое ребро e не из этого подмножества ребер (e ∈ E-F) имеет общую вершину по крайней мере с одним ребром из подмножества F? Если доминирующего подмножества ребер не существует, напечатайте #f. Если доминирующее подмножество ребер существует, напечатайте #t, затем количество ребер в доминирующем подмножестве, а затем список ребер, входящих в доминирующее подмножество. Из всех возможных вариантов доминирующего подмножества выберите вариант с минимальным количеством ребер.
В процессе нахождения решения должна быть предусмотрена визуализация процесса приближения текущего решения задачи к оптимальному. Предусмотрите возможность визуализации результата. Пример входных данных:
((a b) (a c) (a d))
1
Пример печати результата:
#t
1
((a d))

На вход программе подается конъюнктивная нормальная форма, записанная списком списков. Все списки внутри большого списка рассматриваются как дизъюнкции, объединенные конъюнкцией. В каждом списке-дизъюнкции элементами являются символы (например, alpha или x) либо списки из двух элементов (not символ), обозначающие отрицания.
Выполнима ли КНФ, то есть, существует ли набор значений символов, на котором КНФ принимает значение «истина»? Если КНФ выполнима, напечатайте #t и набор значений символов в виде списка списков (символ значение).
В процессе нахождения решения должна быть предусмотрена визуализация процесса поиска решения задачи. Предусмотрите возможность визуализации результата. Пример входных данных:
(((not x1)) (x10 (not x11) x101))
Пример печати результата:
#t
((x1 #f) (x10 #t) (x11 #f) (x101 #t))

На вход программе подается описание взвешенного неориентированного графа G = (V, E) в виде списка описаний ребер. Каждое описание ребра e ∈ E имеет вид (NODE1 NODE2 WEIGHT), где NODE1, NODE2 -- атомы, WEIGHT -- целое положительное число. Затем на вход программе подается целое положительное число K и список ребер L.
Существует ли в графе гамильтонов G цикл, то есть путь, начинающийся и заканчивающийся в одной и той же вершине и проходящий через каждую вершину из графа G только один раз, стоимости не более чем K, включающий в себя все ребра из списка L (и, возможно, другие)? Стоимость пути -- это суммарная стоимость ребер, составляющих путь. Если искомый цикл не существует, напечатайте #f. Если искомый цикл существует, напечатайте #t, далее стоимость цикла, а затем найденный цикл в виде списка. Первым и последним элементом списка должен быть один и тот же атом. Если существует несколько возможных решений, найдите решение с минимальной стоимостью.
В процессе нахождения решения должна быть предусмотрена визуализация процесса приближения текущего решения задачи к оптимальному. Предусмотрите возможность визуализации результата.
Пример входных данных:
((a b 1) (b c 1) (c d 1) (a d 1))
4
((a b) (a d))
Пример печати результата:
#t
4
(a b c d a)

На вход программе подаются два списка длины N (N > 0) список весов предметов W_i (W_i > 0, 1 ≤ i ≤ N) и список их стоимостей C_i (C_i > 0, 1 ≤ i ≤ N). Все веса и стоимости предметов -- целые числа. Затем на вход программе подаются список весов рюкзаков (B_j > 0) и K (K > 0).
Существует ли такой набор K_j -- множеств предметов, положенных в j-ый рюкзак, для которого суммарный вес предметов в каждом K_j не превышает вес рюкзака B_j, любой предмет либо входит в одно из K_j, либо не входит ни в одно, а сумма всех суммарных стоимостей предметов, входящих K_j, не меньше K? Если такого набора не существует, напечатайте #f. Если такой набор существует, напечатайте #t, затем список пар (<список номеров предметов из K_j> <вес предметов K_j>), а затем суммарную стоимость всех предметов, положенных в рюкзаки. Из всех возможных решений выберите такое, которое максимизирует суммарную стоимость предметов в рюкзаках.
В процессе нахождения решения должна быть предусмотрена визуализация процесса приближения текущего решения задачи к оптимальному. Предусмотрите возможность визуализации результата.
Пример входных данных:
(1 1 2 2)
(4 3 2 1)
(3 2)
5
Пример печати результата:
#t
(((1 3) 3) ((2) 1))
9

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