Сложные задачи на Python и на графы

Question

Сложные задачи на Python и на графы

Артём Бардин-Денисов Ученик (120), открыт 6 дней назад

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

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

Определите экспонат, который будет посещаться реже всего. Учитываются только посещения с переходов (то есть посещение в самом начале блуждания не рассматривается).

Формат входных данных: два натуральных числа через пробел, число экспонатов N и число переходов M. Далее идёт M строк, в каждой три числа, первые два – целые номера экспонатов (нумерация с нуля) и вес перехода (вещественное ненулевое число).

Формат выходных данных: единственное целое число, наименее популярный экспонат.

Решение принимается, если выбранный экспонат является одним из трёх наименее популярных, выбранных авторским решением.''
у меня есть частично работающий код но он не всегда выводит правильный ответ:
import random
from collections import defaultdict

def simulate_wandering(N, M, transitions):
# Построение графа
graph = defaultdict(list)
for from_exp, to_exp, weight in transitions:
graph[from_exp].append((to_exp, weight))
graph[to_exp].append((from_exp, weight))

visit_count = [0] * N

current_exhibit = random.randint(0, N - 1)

# Симуляция блуждания
for _ in range(100):
neighbors = graph[current_exhibit]
if not neighbors:
break

# Сумма весов для пропорционального выбора
total_weight = sum(weight for _, weight in neighbors)
rand_value = random.uniform(0, total_weight)
cumulative_weight = 0

for next_exhibit, weight in neighbors:
cumulative_weight += weight
if cumulative_weight >= rand_value:
visit_count[next_exhibit] += 1
current_exhibit = next_exhibit
break

min_visits = min(visit_count)
least_popular_exhibits = [i for i, visits in enumerate(visit_count) if visits == min_visits]

# Для стабильности выбираем минимальный индекс среди наименее популярных
return min(least_popular_exhibits)

# Пример входных данных
N, M = map(int, input().split())
transitions = []

for _ in range(M):
from_exp, to_exp, weight = map(float, input().split())
transitions.append((int(from_exp), int(to_exp), weight))

result = simulate_wandering(N, M, transitions)
print(result)

Дополнен 6 дней назад

Нейросети не могут решить

Answer 1

Код:

 import random  
from collections import defaultdict  
 
def simulate_wandering(N, M, transitions):  
    # Построение графа с учетом нескольких переходов между узлами 
    graph = defaultdict(lambda: defaultdict(float)) 
    for from_exp, to_exp, weight in transitions: 
        graph[from_exp][to_exp] += weight 
        graph[to_exp][from_exp] += weight 
 
    visit_count = [0] * N  
 
    # Начинаем с случайного экспоната 
    current_exhibit = random.randint(0, N - 1)  
 
    # Симуляция блуждания 
    for _ in range(100):  
        neighbors = graph[current_exhibit].items()  
        if not neighbors:   
            break  
 
        # Сумма весов для пропорционального выбора  
        total_weight = sum(weight for _, weight in neighbors)  
        rand_value = random.uniform(0, total_weight)  
        cumulative_weight = 0  
 
        for next_exhibit, weight in neighbors:  
            cumulative_weight += weight  
            if cumulative_weight >= rand_value:  
                visit_count[next_exhibit] += 1  
                current_exhibit = next_exhibit  
                break  
 
 
    min_visits = min(visit_count)  
    least_popular_exhibits = [i for i, visits in enumerate(visit_count) if visits == min_visits]  
 
    # Для стабильности выбираем минимальный индекс среди наименее популярных  
    return min(least_popular_exhibits)  
 
# Пример входных данных  
N, M = map(int, input().split())  
transitions = []  
 
for _ in range(M):  
    from_exp, to_exp, weight = map(float, input().split()) 
    transitions.append((int(from_exp), int(to_exp), float(weight)))   
 
result = simulate_wandering(N, M, transitions)  
print(result)