roboforum.ru

Есть ощущение, что минимум ребер в решении может быть n, а максимум 2n-2. Минимум почему такой - очевидно, а вот максимум - есть у кого мнения, что может больше?

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

Но в худшем случае в граф будет полным и просто будут разные веса ребер.

Добавлено спустя 5 минут 22 секунды:
При поиске методом ветвей и границ можно использовать:

1. Если уже ребер набрали в решение весом больше, чем до этого нашли оптимальней решение - сваливаем;
2. Если компонент слабой связности k, а ребер можем взять еще не более чем k, не выходя за уже найденный минимальный вес - сваливаем;

Вот только я не знаю насколько это оптимизирует перебор, надо всё это брать и ставить эксперименты.

Меня вот другое интересует...
Существует ли какой-то критерий, который бы позволил определить,
насколько мы приблизились к оптимуму? Может мы его нашли уже?
Или наличие такого критерия сразу делает задачу не NP-трудной?

Добавлено спустя 9 минут 9 секунд:
Интересно, в оригинальной постановке задача допускает несколько решений?
Или решением является не какие машины купить, а только сумма, которую надо на них потратить?

Интересно, в оригинальной постановке задача допускает несколько решений?

А если в матрице одинаковые числа?

Нашел я эту задачку...
Там, как мне кажется, (хотя гарантировать, конечно, нельзя)
сильно прореженная матрица (или граф) задается.
Да, нужно в ответе указать какие конкретно машины купить.
И вряд ли условия допускают два одинаковых решения.

Если бот "честный", то он обязан задавать условия так, чтобы было ровно одно решение.

Добавлено спустя 1 час 17 минут 25 секунд:
Создатели задачи конечно понимают, что в общем виде задача нерешаема. Поэтому наверняка исходный граф удовлетворяет неким условиям, которые позволяют найти решение. Поэтому фактически решение состоит из 2 частей : сделать верное предположение о структуре исходного графа, и решить основываясь на этом предположении.

В первую очередь, напрашивается предположение что граф разрежен. Это подтверждается словами одного из решивших задачу: "there are more compounds than you think, but fewer machines"

Добавлено спустя 16 минут 26 секунд:
Вполне возможно, тестовые данные генерятся примерно так: соединяем все n вершин n дугами в кольцо, в каждую вершину входит ровно 1 дуга и выходит ровно 1. Потом случайным образом добавляем некоторое количество дуг, подбирая их вес так, чтобы решение в виде кольца было не оптимальным, и проверяя, чтобы оптимальное решение было единственным.

c ума посходили все

Michael_K писал(а):Нашел я эту задачку...
Там, как мне кажется, (хотя гарантировать, конечно, нельзя)
сильно прореженная матрица (или граф) задается.

Мы делали не так.

Michael_K писал(а):Да, нужно в ответе указать какие конкретно машины купить.
И вряд ли условия допускают два одинаковых решения.

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

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

Не факт, может быть задачу можно решить за N^2*2^N операций, тогда при n=20 это всего 420млн операций.

blindman писал(а):В первую очередь, напрашивается предположение что граф разрежен. Это подтверждается словами одного из решивших задачу: "there are more compounds than you think, but fewer machines"

Если бы я ставил задачу на решение которой надо реально заморочиться - я бы брал пачку тестов - с сильно разреженным графом, с полным графом, почти решение (всего 2-3 ребра выкинуть надо из огромного графа, скажем n=400, кол-во ребер 403) - в общем потребовал бы до кучи выбор алгоритма решения в зависимости от входящего набора данных

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

Мы всегда ставя задачу имели уже какое-то решение и просто под него генерили случайные тесты, добавляя ребра, пока граф не станет сильно связным. Ну и делали 2-3 сгенерированных вручную тестов, типа как я указал n=400, ребер 403.

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

Насчет одного кольца я бы не предполагал - это вряд ли.
Задача генерится "от обратного" - да, вполне может быть.
Хотя может быть и решена (или проверена) полным перебором за неделю.

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

Это по ощущениям... то есть просто предположение.

blindman, а что сервер возвращает в ответ?
Ну, может быть время выполнения вашей программы, сколько она памяти заняла,
или еще какие-нибудь данные? Что-нибудь, чтобы можно было оценить параметры заданий?

blindman, а вы из той же пачки задачки попроще уже решили?

а что сервер возвращает в ответ

Прошел, не прошел.

"не прошел" может означать что угодно - неверный результат, программа не компилируется, и т.п.

"there are more compounds than you think, but fewer machines"

Очевидно полный перебор будет более реален,
а вот проверка на связность - более сложной...

А вы не пробовали тупо полный перебор послать?

Пробовал, не проходит

1. Какую вычислительную сложность имеет сейчас проверка на сильную связность? Можно оптимизировать?
2. Какой подход к перебору? Можно ли установить простейшие отсечения по методу ветвей и границ?

Надо попросить сетара выделить десяток терафлопсов,
а в проге открыть сокет и приконнектиться
Заодно и тестовые данные посмотреть

Ага, типа ты один такой умный