Задача про перекрёсток и счётчики

[oneofother]

Приятного всем существования!
Подскажите, пожалуйста - существует ли способ узнать, что один или несколько счётчиков работают неправильно, если известно следующее:
1. Они считают машины въезжающие и выезжающие с перекрёстка;
2. Один счётчик считает въезжающие и выезжающие машины на одной дороге;
3. Счётчик может ошибаться не только в двух направлениях сразу, но и в каком-то одном;
4. Иногда счётчики ошибаются, но в итоге это очень мало ошибок и это терпимо (если ошибок не более 3% от общего числа посчитанных им машин);
5. На дороге может быть от одного до двух направлений (к перекрёстку, от перекрёстка, и то и другое одновременно);
6. Не существует перекрёстков, состоящих только из въездов на них или только из выездов с них;
7. На перекрёстке могут встречаться 3 и более дорог (хоть бесконечность - мне не жалко, но, скорее всего не более семи-восьми);
8. Иногда, крайне редко, но счётчики на одной-двух дорогах перестают работать совсем;
9. В проверке правильности работы счётчиков используются данные только за средние рабочие дни, крайние рабочие дни отбрасываются (люди едут с дач и на дачи и этим всё портят).

Два дня проб в excel ничего не дали.

[svv]

oneofother в сообщении #1596019 писал(а):

2. Один счётчик считает въезжающие и выезжающие машины на одной дороге;

Он считает раздельно въезжающие и выезжающие машины, или результатом является одно число — их сумма?

Если раздельно, то проверяем первое правило Кирхгофа: суммарное число машин, въехавших на перекрёсток по всем сходящимся в нём дорогам, равно суммарному числу выехавших машин.

Можно сказать, что это единственное, что можно проверить, в следующем смысле. Пусть за период измерений по дорогам $1,2,3,4$ на перекрёсток въехало соответственно $a_1,a_2,a_3,a_4$, а выехало $b_1,b_2,b_3,b_4$ машин, где $a_i,b_i$ — неотрицательные целые числа. Если $a_1+a_2+a_3+a_4=b_1+b_2+b_3+b_4$, к счётчикам претензий быть не может, потому что такая ситуация реализуема.

[oneofother]

svv в сообщении #1596038 писал(а):

Он считает раздельно въезжающие и выезжающие машины, или результатом является одно число — их сумма?

Забыл написать, спасибо что подсказали! Так и есть - четыре счётчика выдают восемь чисел. Каждый по два - въехавшие и выехавшие машины.

svv в сообщении #1596038 писал(а):

суммарное число машин, въехавших на перекрёсток по всем сходящимся в нём дорогам, равно суммарному числу выехавших машин.

Такая проверка не даёт ответа на вопрос - какой же счётчик ошибается (или что вероятно ошибается именно он).

[mihaild]

А конфигурация счетчиков известна (какой на какой дороге стоит)?
И что-то про распределение ошибок - ну там "ошибки, если есть, то распределены нормально? Или можно взять модель "все машины и часть счетчиков захватили враги, какое минимальное количество счетчиков они могли захватить"?

[svv]

Если счётчик ошибается, это обычно ошибка false positive (ложноположительная, машины не было, а её посчитали), или false negative (ложноотрицательная, машина проехала, а её не посчитали)?

[Alex Krylov]

svv в сообщении #1596038 писал(а):

oneofother в сообщении #1596019 писал(а):

2. Один счётчик считает въезжающие и выезжающие машины на одной дороге;

Он считает раздельно въезжающие и выезжающие машины, или результатом является одно число — их сумма?

Если раздельно, то проверяем первое правило Кирхгофа: суммарное число машин, въехавших на перекрёсток по всем сходящимся в нём дорогам, равно суммарному числу выехавших машин.

Тут можно даже нечто вот такое рассмотреть (при соотв. допущениях): $\min\limits_{\left\lbrace\hat{I_i}\right\rbrace} \sum\limits_{i=1}^{n}(I_i-\hat{I_i})^2, \boldsymbol{M} \hat{I}=0, \hat{I_i}\in\mathbb{N}, i=1..n$, где $\boldsymbol{M}$ - матрица инцидентности ориентированного графа.

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

[svv]

mihaild в сообщении #1596043 писал(а):

А конфигурация счетчиков известна (какой на какой дороге стоит)?

Я думаю, можно ещё рассчитывать на то, что счётчики установлены на всех дорогах, которые сходятся в одном перекрёстке, но не на то, что они установлены на всех перекрёстках какого-то участка дороги (включая средние и мелкие ответвления).

То есть проверки возможны, скорее, "вершинные", чем "рёберные". (Тема называется «Задача про перекрёсток и счётчики»)

[Rak so dna]

Сразу хотел написать категорический ответ, но увидев быстро растущее количество сообщений, пожалуй воздержусь...

Пусть, для определённости, у нас есть перекрёсток из четырёх двунаправленных дорог, и четыре счётчика — по одному на каждой из них

Может я чего не понял, но в такой постановке вопроса никакая проверка ничего не даст (как мне кажется). Я считаю, что можно под любые данные на счётчиках подобрать ситуации, при которых количество неисправных счётчиков будет любым на выбор от $1$ до $4$. Если приведёте какой-нибудь набор показаний, по которому можно хоть что-то определить (кроме тривиального, что существует хотя бы один нерабочий счётчик) буду благодарен.

[oneofother]

svv в сообщении #1596048 писал(а):

mihaild в сообщении #1596043 писал(а):

А конфигурация счетчиков известна (какой на какой дороге стоит)?

Я думаю, можно ещё рассчитывать на то, что счётчики установлены на всех дорогах, которые сходятся в одном перекрёстке, но не на то, что они установлены на всех перекрёстках какого-то участка дороги (включая средние и мелкие ответвления).

Когда родилась эта задачка, предполагалось, что на углах перекрёстка стоят люди и считают, каждый свою дорогу, обе стороны, но один из них лжец (привет книжке "Принцесса и тигр"). Возник вопрос - можно ли выявить лжеца, имея много данных, похожих на эти:

А, да, лжец не сразу себя проявляет! Мы подумали, что можно построить каким-то образом график, на котором станет видно, что один из счётчиков стал вести себя не так в некий момент времени.

[Rak so dna]

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

[Sender]

Даже если достоверно известно, что неисправен ровно один счётчик, и он всегда за день завышает въезд ровно на единицу, не трогая выезд, мы всё равно никак не можем понять, какой именно, с равным успехом это может оказаться любой.

[svv]

Понятно. Лжец — это, например, счётчик, который отлучался на полчаса в кафе, но утверждает, что честно отстоял на посту всё время.

oneofother в сообщении #1596050 писал(а):

Возник вопрос - можно ли выявить лжеца, имея много данных, похожих на эти

Без дополнительных предположений о характере "ошибок" лжеца — точно нет. Потому что, в Вашем примере, уменьшив "въездные" суточные показания одного любого счётчика на единицу (или увеличив "выездные" показания одного любого счётчика на единицу), мы получим возможную, реализуемую ситуацию.

svv в сообщении #1596038 писал(а):

Если $a_1+a_2+a_3+a_4=b_1+b_2+b_3+b_4$, к счётчикам претензий быть не может, потому что такая ситуация реализуема.

[Alex Krylov]

svv в сообщении #1596048 писал(а):

mihaild в сообщении #1596043 писал(а):

А конфигурация счетчиков известна (какой на какой дороге стоит)?

Я думаю, можно ещё рассчитывать на то, что счётчики установлены на всех дорогах, которые сходятся в одном перекрёстке, но не на то, что они установлены на всех перекрёстках какого-то участка дороги (включая средние и мелкие ответвления).

То есть проверки возможны, скорее, "вершинные", чем "рёберные". (Тема называется «Задача про перекрёсток и счётчики»)

Любые проверки, попытки коррекции (за счет внутренних связей и избыточности) будут иметь смысл, если при определенных условиях (плотный трафик, освещенность, гидрометеоры итд) ошибки не возникают во всех (или во многих) счетчиках сразу. А у ТС ничего не говорится о характере ошибок, их причине, статистике.

Например, в спутниковой навигации многие алгоритмы обнаружения/коррекции аномалий базируются на том факте, что вероятность ошибочной работы одного спутника очень мала, а вероятность ошибочной работы одновременно двух и более спутников ПРЕНЕБРЕЖИМО мала. Поэтому можно ранжировать навигационные решения по норме невязки (или её квадрату). При отсутствии аномалий квадрат нормы невязки имеет Хи-квадрат распределение, а при поддающейся детектированию аномалии - нецентральное Хи-квадрат распределение (характеризуемое параметром нецентральности). На самом деле все несколько хуже: если мы для Метода Наименьших Квадратов запишем матрицу, транслирующую вектор ошибки измерений в вектор невязки, то увидим, что эта матрица имеет нетривиальное ядро, т.е. возможна сколь угодно большая по модулю ошибка с нулевой нормой невязки (т.е. такую ошибку нельзя отловить с помощью Хи-, Хи-квадрат статистик).

[Rak so dna]

(Просто любопытно)

oneofother в сообщении #1596019 писал(а):

Два дня проб в excel ничего не дали.

А что конкретно вы пробовали два дня?

[Rak so dna]

Sender в сообщении #1596052 писал(а):

Даже если достоверно известно, что неисправен ровно один счётчик, и он всегда за день завышает въезд ровно на единицу, не трогая выезд, мы всё равно никак не можем понять, какой именно, с равным успехом это может оказаться любой.

Ну всё-таки в этом случае есть ситуации, когда мы точно можем определить неисправный счётчик. Например, когда у трёх счётчиков показания по въезду равны нулю.

-- 02.06.2023, 08:44 --

Alex Krylov в сообщении #1596056 писал(а):

Любые проверки, попытки коррекции (за счет внутренних связей и избыточности) будут иметь смысл, если при определенных условиях (плотный трафик, освещенность, гидрометеоры итд) ошибки не возникают во всех (или во многих) счетчиках сразу. А у ТС ничего не говорится о характере ошибок, их причине, статистике.

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