Динамическое программирование

[QWERTY2468]

В службу розыска поступило заявление о пропаже человека. На схематической карте весь город, контролируемый данной службой, представлен в виде круга. Весь круг разделен на некоторое количество сегментов (например, 12). Для поиска данная служба выделяет некоторое количество команд, меньшее чем количество секторов. По промежуточным результатам расследования установлена ​​возможность нахождения человека в каждом из частей. Кроме того служба поиска опирается в своих расследованиях на то, что если объект находится на участке размера S, то вероятность того, что m команд, производящих поиск на данном участке, найдут данный объект, равна

P = (e ^ (-k1 * S)) * (1 - e ^ (-k2 * m)),

где k1 , k2 – положительные заранее известные константы.
Определить количество команд, которое службе розыска следует направить на каждый из секторов.

Как решать?

[Valick]

Сообщение от QWERTY2468

Для поиска данная служба выделяет некоторое количество команд, меньшее чем количество секторов

Сообщение от QWERTY2468

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

Вот теперь хз.

[macomics]

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

[QWERTY2468]

Сообщение от macomics

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

Зачем ты пишешь, если не знаешь!
А ты ник как придумал? Об клаву головой?

[macomics]

Сообщение от QWERTY2468

В службу розыска поступило заявление о пропаже человека. На схематической карте весь город, контролируемый данной службой, представлен в виде круга. Весь круг разделен на некоторое количество сегментов (например, 12). Для поиска данная служба выделяет некоторое количество команд, меньшее чем количество секторов. По промежуточным результатам расследования установлена ​​возможность нахождения человека в каждом из частей. Кроме того служба поиска опирается в своих расследованиях на то, что если объект находится на участке размера S, то вероятность того, что m команд, производящих поиск на данном участке, найдут данный объект, равна

P = (e ^ (-k1 * S)) * (1 - e ^ (-k2 * m)),

где k1 , k2 – положительные заранее известные константы.
Определить количество команд, которое службе розыска следует направить на каждый из секторов.

Как решать?

Ищешь халяву вне фриланс?

[QWERTY2468]

Сообщение от macomics

Ищешь халяву вне фриланс?

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

[сфинкс]

допустим протекает крыша и каждый подставленный таз
ловит капли с вероятностью 52%
сколько тазов нужно для надёжности 98%

0,98 = 1-(1-0,52)^N
0,98-1 = -0,48^N

ln(0,02) = N*ln0,48

N = ln(0,02)/ln0,48 = -3,912/-0,734 = 5,33

значит нужно 5,33 или 6 таза

зато как применить к задаче темы не знаю

[Пётр Седов]

Valick, я думаю там имеется в виду, что в некоторые секторы придётся послать 0 команд. Не особо знаю теорию вероятностей, но вроде так:
<вероятность, что человека найдут хотя бы в одном искомом секторе>
= 1 - <вероятность, что человека не найдут ни в одном искомом секторе>
= 1 - <вероятность, что человека не найдут в первом искомом секторе> * <вероятность, что человека не найдут во втором искомом секторе> * ... * <вероятность, что человека не найдут в последнем искомом секторе>
= 1 - (1 - <вероятность, что человека найдут в первом искомом секторе>) * (1 - <вероятность, что человека найдут во втором искомом секторе>) * ... * (1 - <вероятность, что человека найдут в последнем искомом секторе>)
= 1 - (1 - <P для первого искомого сектора>) * (1 - <P для второго искомого сектора>) * ... * (1 - <P для последнего искомого сектора>)
Вот эту величину надо максимизировать, для всех возможных вариантов. Если делать тупой перебор, то это примерно так:

#include <assert.h>
#include <math.h>
#include <stdio.h>

const int _sectors_count = 12;
const int _teams_count = 5;

struct sector_t {
  double area; // S
  int teams_count; // m
};
sector_t _sectors[_sectors_count];

int _case_index = 0;
double _max_prob_find = -1;
int _best_case_index = -1;

void send_teams(int sector_index, int available_teams_count);
void check_case();

int main() {
  _sectors[0].area = 1;
  _sectors[1].area = 2;
  _sectors[2].area = 3;
  _sectors[3].area = 1;
  _sectors[4].area = 2;
  _sectors[5].area = 3;
  _sectors[6].area = 1;
  _sectors[7].area = 2;
  _sectors[8].area = 3;
  _sectors[9].area = 1;
  _sectors[10].area = 2;
  _sectors[11].area = 3;
  send_teams(0, _teams_count);
  printf("best case: %i, probability of find = %.3f\n", _best_case_index, _max_prob_find);
  return 0;
}

void send_teams(int sector_index, int available_teams_count) {
  if (sector_index == _sectors_count - 1) { // если последний сектор
    _sectors[sector_index].teams_count = available_teams_count;
    check_case();
    return;
  }

  for (int i = 0; i <= available_teams_count; i++) {
    _sectors[sector_index].teams_count = i;
    send_teams(sector_index + 1, available_teams_count - i);
  }
}

void check_case() {
  const double k1 = 1;
  const double k2 = 1;
  printf("case %i:\n", _case_index);
  int sum = 0;
  double prob_not_find = 1;
  for (int i = 0; i < _sectors_count; i++) {
    int teams_count = _sectors[i].teams_count;
    assert(teams_count >= 0);
    if (teams_count != 0) {
      sum += teams_count;
      printf("  sector %i: %i team(s)\n", i, teams_count);
      double prob_find = exp(-k1 * _sectors[i].area) * (1 - exp(-k2 * teams_count));
      prob_not_find *= 1 - prob_find;
    }
  }
  assert(sum == _teams_count);
  double prob_find = 1 - prob_not_find;
  printf("  probability of find = %.3f\n", prob_find);
  if (prob_find > _max_prob_find) {
    _max_prob_find = prob_find;
    _best_case_index = _case_index;
  }
  _case_index++;
}

Сообщение от сфинкс

0,98 = 1-(1-0,52)^N

У меня похожая формула получилась.